{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Increasing Subsequence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #queue #array #divide-and-conquer #dynamic-programming #monotonic-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #队列 #数组 #分治 #动态规划 #单调队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLIS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长递增子序列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>找到&nbsp;<code>nums</code>&nbsp;中满足以下要求的最长子序列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子序列 <strong>严格递增</strong></li>\n",
    "\t<li>子序列中相邻元素的差值 <strong>不超过</strong>&nbsp;<code>k</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回满足上述要求的 <strong>最长子序列</strong>&nbsp;的长度。</p>\n",
    "\n",
    "<p><strong>子序列</strong>&nbsp;是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [4,2,1,4,3,4,5,8,15], k = 3\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "满足要求的最长子序列是 [1,3,4,5,8] 。\n",
    "子序列长度为 5 ，所以我们返回 5 。\n",
    "注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [7,4,5,1,8,12,4,7], k = 5\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>\n",
    "满足要求的最长子序列是 [4,5,8,12] 。\n",
    "子序列长度为 4 ，所以我们返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,5], k = 1\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "满足要求的最长子序列是 [1] 。\n",
    "子序列长度为 1 ，所以我们返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-increasing-subsequence-ii](https://leetcode.cn/problems/longest-increasing-subsequence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-increasing-subsequence-ii](https://leetcode.cn/problems/longest-increasing-subsequence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,1,4,3,4,5,8,15]\\n3', '[7,4,5,1,8,12,4,7]\\n5', '[1,5]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "f(i) 以下标i结尾的子序列最大长度\n",
    "j < i and nums[i] - nums[j] <= k\n",
    "nums[j] >= nums[i] - k\n",
    "f(i) = max(f(j) + 1, f(i))\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "  def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "    n = len(nums)\n",
    "    bit = BinaryIndexedTree(10**5)\n",
    "    ans = 1\n",
    "    for x in nums:\n",
    "      cur = bit.query_range(x - k, x - 1) + 1\n",
    "      ans = max(ans, cur)\n",
    "      bit.update(x, cur)\n",
    "    return ans\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "    self.origin_arr = [0] * (n + 1)\n",
    "  def update(self, i, x):\n",
    "    self.origin_arr[i] = x\n",
    "    while i < len(self.tree) and x > self.tree[i]:\n",
    "      self.tree[i] = x\n",
    "      i += i & -i\n",
    "  def query_range(self, l, r):\n",
    "    l = max(l, 1)\n",
    "    ans = 0\n",
    "    while r >= l:\n",
    "      next = r - (r & -r)\n",
    "      if next + 1 >= l:\n",
    "        ans = max(ans, self.tree[r])\n",
    "        r = next\n",
    "      else:\n",
    "        ans = max(ans, self.origin_arr[r])\n",
    "        r -= 1\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def bit_ceil(x):\n",
    "    a = 1\n",
    "    while a < x: a *= 2\n",
    "    return a\n",
    "\n",
    "class segtree2:\n",
    "    def __init__(self, n, e, op) -> None:\n",
    "        self.fun_e = e\n",
    "        self.fun_op = op\n",
    "        self.n = bit_ceil(n)\n",
    "        import math\n",
    "        self.log = int(math.log2(self.n)) # 说明中间节点有几层\n",
    "\n",
    "        self.arr = [e() for _ in range(2 * self.n)]\n",
    "        for i in range(self.n - 1, 0, -1):\n",
    "            self._update(i)\n",
    "        \n",
    "    def _update(self, i):\n",
    "        self.arr[i] = self.fun_op(self.arr[i * 2], self.arr[i * 2 + 1])\n",
    "\n",
    "    def set(self, i, x): # 从0开始\n",
    "        i += self.n\n",
    "        self.arr[i] = x\n",
    "\n",
    "        for j in range(1, self.log + 1):\n",
    "            self._update(i >> j) \n",
    "\n",
    "    def get(self, i): # 从0开始\n",
    "        return self.arr[i + self.n]\n",
    "    \n",
    "    def prod(self, le, ri): # 左开右闭区间\n",
    "        assert 0 <= le and le <= ri and ri <= self.n\n",
    "        le += self.n\n",
    "        ri += self.n\n",
    "        a, b = self.fun_e(), self.fun_e()\n",
    "\n",
    "        while le < ri:\n",
    "            if le & 1 == 1: # 该叶子节点是父节点的右孩子节点\n",
    "                a = self.fun_op(a, self.arr[le])\n",
    "                le += 1\n",
    "            if ri & 1 == 1:\n",
    "                ri -= 1\n",
    "                b = self.fun_op(self.arr[ri], b)\n",
    "            le >>= 1\n",
    "            ri >>= 1\n",
    "\n",
    "        return self.fun_op(a, b)\n",
    "\n",
    "    def all_prod(self):\n",
    "        return self.arr[1]\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = max(nums)\n",
    "        seg = segtree2(n + 1, lambda: 0, max)\n",
    "        for i, x in enumerate(nums):\n",
    "            a = seg.prod(max(0, x - k), x)\n",
    "            b = a + 1\n",
    "            c = seg.get(x)\n",
    "            seg.set(x, max(c, b))\n",
    "            # print([i, x], b)\n",
    "        return seg.all_prod()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, n:int, init) -> None:\n",
    "        bit_num = (n-1).bit_length()\n",
    "        self.tree = [init] * ((1<<bit_num+1)-1)\n",
    "        self.head = (1<<bit_num) - 1\n",
    "\n",
    "    def update(self, i, x):\n",
    "        k = self.head+i\n",
    "        while k >= 0:\n",
    "            self.tree[k] = max(self.tree[k], x) \n",
    "            k = (k-1) // 2\n",
    "        \n",
    "    def query(self, l, r):\n",
    "        l += self.head\n",
    "        r += self.head\n",
    "        if l == r:\n",
    "            return self.tree[l]\n",
    "        if r < l:\n",
    "            return 0\n",
    "        vl = self.tree[l] \n",
    "        vr = self.tree[r]   \n",
    "        while l != r - 1:\n",
    "            if l & 1 == 1:\n",
    "                vl = max(vl, self.tree[l+1])\n",
    "\n",
    "            if r & 1 == 0:\n",
    "                vr = max(vr, self.tree[r-1])\n",
    "            \n",
    "            l = (l-1) >> 1\n",
    "            r = (r-1) >> 1\n",
    "        return max(vl, vr)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k) -> int:\n",
    "        mx = max(nums)\n",
    "        seg = SegTree(mx+1, 0)\n",
    "        for i, x in enumerate(nums):\n",
    "            s = seg.query(max(1, x-k), x-1)\n",
    "            seg.update(x, s + 1)\n",
    "\n",
    "        return seg.query(1, mx)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, n:int, init) -> None:\n",
    "        bit_num = (n-1).bit_length()\n",
    "        self.tree = [init] * ((1<<bit_num+1)-1)\n",
    "        self.head = (1<<bit_num) - 1\n",
    "\n",
    "    def update(self, i, x):\n",
    "        k = self.head+i\n",
    "        while k >= 0:\n",
    "            self.tree[k] = max(self.tree[k], x) \n",
    "            k = (k-1) // 2\n",
    "        \n",
    "    def query(self, l, r):\n",
    "        l += self.head\n",
    "        r += self.head\n",
    "        if l == r:\n",
    "            return self.tree[l]\n",
    "        if r < l:\n",
    "            return 0\n",
    "        vl = self.tree[l] \n",
    "        vr = self.tree[r]   \n",
    "        while l != r - 1:\n",
    "            if l & 1 == 1:\n",
    "                vl = max(vl, self.tree[l+1])\n",
    "\n",
    "            if r & 1 == 0:\n",
    "                vr = max(vr, self.tree[r-1])\n",
    "            \n",
    "            l = (l-1) >> 1\n",
    "            r = (r-1) >> 1\n",
    "        return max(vl, vr)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k) -> int:\n",
    "        mx = max(nums)\n",
    "        seg = SegTree(mx+1, 0)\n",
    "        for i, x in enumerate(nums):\n",
    "            s = seg.query(max(1, x-k), x-1)\n",
    "            seg.update(x, s + 1)\n",
    "\n",
    "        return seg.query(1, mx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,n):\n",
    "        self.max=[0]*(4*n)\n",
    "    \n",
    "    def update(self,o,l,r,idx,val):\n",
    "        if l==r:\n",
    "            self.max[o]=max(self.max[o],val)\n",
    "            return\n",
    "        mid=(l+r)//2\n",
    "        if mid>=idx:\n",
    "            self.update(o*2,l,mid,idx,val)\n",
    "        else:\n",
    "            self.update(o*2+1,mid+1,r,idx,val)\n",
    "        self.max[o]=max(self.max[2*o],self.max[2*o+1])\n",
    "\n",
    "    def query(self,o,l,r,L,R):\n",
    "        if l>=L and r<=R:\n",
    "            return self.max[o]\n",
    "        mid=(l+r)//2\n",
    "        res=0\n",
    "        if mid>=L:\n",
    "            res=max(res,self.query(o*2,l,mid,L,R))\n",
    "        if mid+1<=R:\n",
    "            res=max(res,self.query(o*2+1,mid+1,r,L,R))\n",
    "        return res     \n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n=max(nums)\n",
    "        st=SegTree(n)\n",
    "        for num in nums:\n",
    "            q=st.query(1,1,n,max(1,num-k),num-1) if num-1>=1 else 0\n",
    "            st.update(1,1,n,num,1+q)\n",
    "        return st.max[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree():\n",
    "    def __init__(self, nums: list[int]) -> None:\n",
    "        n = len(nums)\n",
    "        d = [0] * (4 * n)\n",
    "        self.nums = nums\n",
    "        self.n = n\n",
    "        self.d = d\n",
    "        self.build(0, 0, n - 1)\n",
    "\n",
    "    def pushup(self, i: int) -> None:\n",
    "        d = self.d\n",
    "        d[i] = max(d[2 * i + 1], d[2 * i + 2])\n",
    "\n",
    "    def pushdown(self, i: int, l: int, r: int) -> None:\n",
    "        d, b = self.d, self.b\n",
    "        m = (l + r) // 2\n",
    "        b[2 * i + 1] += b[i]\n",
    "        b[2 * i + 2] += b[i]\n",
    "        d[2 * i + 1] += (m - l + 1) * b[i]\n",
    "        d[2 * i + 2] += (r - m) * b[i]\n",
    "        b[i] = 0\n",
    "\n",
    "    def build(self, i: int, l: int, r: int) -> None:\n",
    "        nums, d = self.nums, self.d\n",
    "        if l == r:\n",
    "            d[i] = nums[l]\n",
    "            return\n",
    "        m = (l + r) // 2\n",
    "        self.build(2 * i + 1, l, m)\n",
    "        self.build(2 * i + 2, m + 1, r)\n",
    "        self.pushup(i)\n",
    "    \n",
    "    def update(self, i: int, l: int, r: int, x: int, L: int, R: int) -> None:\n",
    "        d = self.d\n",
    "        if L <= l and r <= R:\n",
    "            d[i] = max(d[i], x)\n",
    "            return\n",
    "        m = (l + r) // 2\n",
    "        if m >= L:\n",
    "            self.update(2 * i + 1, l, m, x, L, R)\n",
    "        if m < R:\n",
    "            self.update(2 * i + 2, m + 1, r, x, L, R)\n",
    "        self.pushup(i)\n",
    "\n",
    "    def query(self, i: int, l: int, r: int, L: int, R: int) -> int:\n",
    "        d = self.d\n",
    "        if L <= l and r <= R:\n",
    "            return d[i]\n",
    "        mx = 0\n",
    "        m = (l + r) // 2\n",
    "        if m >= L:\n",
    "            mx = max(mx, self.query(2 * i + 1, l, m, L, R))\n",
    "        if m < R:\n",
    "            mx = max(mx, self.query(2 * i + 2, m + 1, r, L, R))\n",
    "        return mx\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        m = max(nums)\n",
    "        st = SegmentTree([0] * (max(nums) + 1))\n",
    "        for x in nums:\n",
    "            res = st.query(0, 0, m, max(x - k, 0), x - 1) + 1\n",
    "            st.update(0, 0, m, res, x, x)\n",
    "        return st.query(0, 0, m, 0, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nodes = None\n",
    "\n",
    "def update(idx, start, end, l, r, val):\n",
    "    global nodes\n",
    "    if(l<=start and r>=end):\n",
    "        nodes[idx] = max(nodes[idx], val)\n",
    "        return\n",
    "    mid = (start+end)>>1\n",
    "    if l<=mid:\n",
    "        update(2*idx+1, start, mid, l, r, val)\n",
    "    if r>=mid+1:\n",
    "        update(2*idx+2, mid+1, end, l, r, val)\n",
    "    nodes[idx] = max(nodes[2*idx+1], nodes[2*idx+2])\n",
    "\n",
    "    \n",
    "def query(idx, start, end, l, r):\n",
    "    global nodes\n",
    "    if(l<=start and r>=end):\n",
    "        return nodes[idx]\n",
    "    mid = (start+end)>>1\n",
    "    ans = 0\n",
    "    if l<=mid:\n",
    "        ans = max(ans, query(2*idx+1, start, mid, l, r))\n",
    "    if r>=mid+1:\n",
    "        ans = max(ans, query(2*idx+2, mid+1, end, l, r))\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        global nodes\n",
    "        nodes = [0] * (4*10**5)\n",
    "        ans = 0\n",
    "\n",
    "        for num in nums:\n",
    "            val = query(0, 0, 10**5, max(0, num-k), max(0, num-1))\n",
    "            ans = max(ans, val+1)\n",
    "            update(0, 0, 10**5, num, num, val+1)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class STree:\n",
    "    def __init__(self, size):\n",
    "        self.arr = [0] * size\n",
    "        self.lazy = [False] * size\n",
    "\n",
    "    def query(self, o, lt, rt, L, R):\n",
    "        if R < lt or rt < L:\n",
    "            return 0\n",
    "        if L <= lt and rt <= R:\n",
    "            return self.arr[o]        \n",
    "        \n",
    "        if self.lazy[o]:\n",
    "            self.arr[2*o] = max(self.arr[o], self.arr[2*o])\n",
    "            self.arr[2*o+1] = max(self.arr[o], self.arr[2*o+1])\n",
    "            self.lazy[2*o] = self.lazy[2*o+1] = True\n",
    "            self.lazy[o] = False\n",
    "        \n",
    "        m = (lt + rt) // 2\n",
    "        ans = 0\n",
    "        if lt <= m:\n",
    "            ans = max(ans, self.query(2*o, lt, m, L, R))\n",
    "        if m < rt:\n",
    "            ans = max(ans, self.query(2*o+1, m+1, rt, L, R))\n",
    "        return ans\n",
    "\n",
    "    def update(self, o, lt, rt, L, R, val):\n",
    "        if R < lt or rt < L:\n",
    "            return\n",
    "        if L <= lt and rt <= R:\n",
    "            self.arr[o] = max(self.arr[o], val)\n",
    "            self.lazy[o] = True\n",
    "            return\n",
    "        \n",
    "        if self.lazy[o]:\n",
    "            self.arr[2*o] = max(self.arr[o], self.arr[2*o])\n",
    "            self.arr[2*o+1] = max(self.arr[o], self.arr[2*o+1])\n",
    "            self.lazy[2*o] = self.lazy[2*o+1] = True\n",
    "            self.lazy[o] = False\n",
    "        \n",
    "        m = (lt + rt) // 2        \n",
    "        if lt <= m:\n",
    "            self.update(2*o, lt, m, L, R, val)\n",
    "        if m < rt:\n",
    "            self.update(2*o+1, m+1, rt, L, R, val)\n",
    "        self.arr[o] = max(self.arr[2*o], self.arr[2*o+1])\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = max(nums)\n",
    "        st = STree(4*n)\n",
    "        for a in nums:            \n",
    "            if a == 1:\n",
    "                cur = 1\n",
    "                st.update(1, 0, n, 1, 1, 1)\n",
    "            else:\n",
    "                cur = st.query(1, 0, n, max(1, a-k), max(1, a-1)) + 1                              \n",
    "                st.update(1, 0, n, a, a, cur)\n",
    "            ans = max(ans, cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "\n",
    "    def __init__(self, nums, fn) -> None:\n",
    "        n = len(nums)\n",
    "        self.n = n\n",
    "        self.nums = nums\n",
    "        self.mn = [0] * (4 * n)\n",
    "        self.todo = [0] * (4 * n)\n",
    "        self.fn = fn\n",
    "\n",
    "    def update(self, o: int, l: int, r: int, i: int, val: int) -> None:  # 单点更新。更新i\n",
    "        if l == r:\n",
    "            self.mn[o] = val\n",
    "            return\n",
    "        m = (l + r) // 2\n",
    "        if i <= m:\n",
    "            self.update(o * 2, l, m, i, val)\n",
    "        else:\n",
    "            self.update(o * 2 + 1, m + 1, r, i, val)\n",
    "        self.push_up(o)\n",
    "\n",
    "    def push_up(self, o):\n",
    "        self.mn[o] = self.fn(self.mn[o * 2], self.mn[o * 2 + 1])\n",
    "\n",
    "    # 返回区间 [L,R] 内的最大值\n",
    "    def query(self, o: int, l: int, r: int, L: int, R: int) -> int:  # L 和 R 在整个递归过程中均不变，将其大写，视作常量\n",
    "        if L <= l and r <= R: return self.mn[o]\n",
    "        res = 0\n",
    "        m = (l + r) // 2\n",
    "        if L <= m: res = self.query(o * 2, l, m, L, R)\n",
    "        if R > m: res = self.fn(res, self.query(o * 2 + 1, m + 1, r, L, R))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        u = max(nums)\n",
    "        sgt = SegmentTree([0] * u, max)\n",
    "        for num in nums:\n",
    "            if num == 1:\n",
    "                sgt.update(1, 1, u, 1, 1)\n",
    "            else:\n",
    "                tmp = 1 + sgt.query(1, 1, u, max(num - k, 1), num - 1)\n",
    "                sgt.update(1, 1, u, num, tmp)\n",
    "        return sgt.query(1, 1, u, 1, u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, n, k):\n",
    "        self.n = n\n",
    "        self.k = k\n",
    "        self.nodes = [0] * (4 * n)\n",
    "        self.lazy = [False] * (4 * n)\n",
    "        \n",
    "    def update(self, index, left, right, val):\n",
    "        n = self.n\n",
    "        k = self.k\n",
    "        if left == right:\n",
    "            self.nodes[index] = max(self.nodes[index], 1 + self.query(1, 1, n, max(val - k, 1), val - 1))\n",
    "            return\n",
    "        mid = (left + right) // 2\n",
    "        if mid >= val:\n",
    "            self.update(index * 2, left, mid, val)\n",
    "        else:\n",
    "            self.update(index * 2 + 1, mid + 1, right, val)\n",
    "        self.nodes[index] = max(self.nodes[index * 2], self.nodes[index * 2 + 1])\n",
    "\n",
    "    def query(self, index, left, right, lb, rb):\n",
    "        if rb == 0:\n",
    "            return 0\n",
    "        if lb <= left and right <= rb:\n",
    "            return self.nodes[index]\n",
    "        res = 0\n",
    "        mid = (left + right) // 2\n",
    "        if lb <= mid:\n",
    "            res = max(res, self.query(index * 2, left, mid, lb, rb))\n",
    "        if mid < rb:\n",
    "            res = max(res, self.query(index * 2 + 1, mid + 1, right, lb, rb))\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        ma = max(nums)\n",
    "        st = SegmentTree(ma, k)\n",
    "        for num in nums:\n",
    "            st.update(1, 1, ma, num)\n",
    "        return st.nodes[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "        self.n = len(nums)\n",
    "        self.d = [0]*(4*self.n)\n",
    "        self.lazy = [0]*(4*self.n)\n",
    "        self.build(1,1,self.n)\n",
    "        # print(self.d)\n",
    "\n",
    "    def build(self, p ,start, end):\n",
    "        # print(s,t,p)\n",
    "        if start == end:\n",
    "            self.d[p]=self.nums[start-1]\n",
    "            return \n",
    "        mid = start+(end-start)//2\n",
    "        self.build(p*2, start, mid)\n",
    "        self.build(p*2+1, mid+1, end)\n",
    "        self.pushUp(p)    \n",
    "    def pushDown(self, p, start, end):\n",
    "        if self.lazy[p] == 0:\n",
    "            return \n",
    "        mid = start + (end - start)//2\n",
    "        self.lazy[p*2] += self.lazy[p]\n",
    "        self.lazy[p*2+1] += self.lazy[p]\n",
    "        self.d[p*2] = (mid-start+1) * self.lazy[p]\n",
    "        self.d[p*2+1] = (end - mid) * self.lazy[p]\n",
    "        self.lazy[p] = 0    \n",
    "    def pushUp(self, p):\n",
    "        self.d[p] = max(self.d[p*2], self.d[p*2+1])\n",
    "    def update(self,left,right,value):\n",
    "        self._update(1,1,self.n,left,right,value)\n",
    "\n",
    "    def _update(self,p, start, end, left, right, value):\n",
    "        if left<=start and end<=right:\n",
    "            self.d[p] = value\n",
    "            self.lazy[p] += value\n",
    "            return\n",
    "        mid = start+(end-start)//2\n",
    "        self.pushDown(p, start,end)\n",
    "        if left<=mid:\n",
    "            self._update(p*2,start,mid,left,right,value)\n",
    "        if right>mid:\n",
    "            self._update(p*2+1,mid+1,end,left,right,value)\n",
    "        self.pushUp(p)\n",
    "    def query(self, left,right):\n",
    "        return self._query(1, 1, self.n, left, right)\n",
    "\n",
    "    def _query(self,p, start, end, left, right):\n",
    "        if left <= start and end <= right:\n",
    "            return self.d[p]\n",
    "        mid = start + (end - start) // 2\n",
    "        self.pushDown(p, start, end)\n",
    "        ans = 0\n",
    "        if left <= mid:\n",
    "            ans = max(ans, self._query(p*2, start, mid, left, right))\n",
    "        if right > mid:\n",
    "            ans = max(ans, self._query(p*2+1, mid+1, end, left, right))\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 10**5 and k == 1:\n",
    "            return 10**5\n",
    "        mx = max(nums)\n",
    "        f = [0]*(mx)\n",
    "        t = SegmentTree(f)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            x = 0\n",
    "            if num == 1:\n",
    "                x = 1\n",
    "            else:\n",
    "                x = t.query(max(1,num - k), num - 1)+1\n",
    "            t.update(num,num,x)\n",
    "            ans = max(ans, x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        ss = sorted(set([x for x in nums]+[x-k for x in nums]))\n",
    "        n = len(ss)\n",
    "        mx = [0] * 2 * n\n",
    "        def add(i,v):\n",
    "            i += n\n",
    "            mx[i] = v\n",
    "            while i:\n",
    "                i >>= 1\n",
    "                mx[i] = max(mx[i << 1],mx[i << 1 | 1])\n",
    "        def query(s,e):\n",
    "            s += n\n",
    "            e += n\n",
    "            res = 0\n",
    "            while s <= e:\n",
    "                if s & 1:\n",
    "                    res = max(res,mx[s])\n",
    "                    s += 1\n",
    "                if not (e & 1):\n",
    "                    res = max(res,mx[e])\n",
    "                    e -= 1\n",
    "                s >>= 1\n",
    "                e >>= 1\n",
    "            return res\n",
    "        for x in nums:\n",
    "            t = bisect_left(ss,x-k)\n",
    "            x = bisect_left(ss,x) \n",
    "            xx = query(t,x-1) + 1\n",
    "            add(x,xx)\n",
    "        return mx[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # 求解 lis问题的优化方法：\n",
    "        # 1. 维护固定长度的is的末尾元素的最小值 + 二分\n",
    "        # 2. 基于值域的线段树， 平衡树\n",
    "\n",
    "        # 1. 线段树： 基于分治的二叉树\n",
    "        # 差值不超过k的约束，使用线段树更好处理\n",
    "        # f[i][j] 表示nums的前i个元素中，以元素结尾的满足题目两个条件的子序列的最长长度\n",
    "        # u = max(nums)\n",
    "        # mx = [0] * (4 * u)\n",
    "\n",
    "        # def modify(o:int, l:int, r:int, i:int, val:int)-> None:\n",
    "        #     if l == r:\n",
    "        #         mx[o] = val\n",
    "        #         return\n",
    "        #     m = (l + r) // 2\n",
    "        #     if i <= m: modify(o * 2, l, m, i, val)\n",
    "        #     else: modify(o * 2 + 1, m + 1, r, i, val)\n",
    "        #     mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "\n",
    "        # def query(o:int, l:int, r:int, L:int, R:int)->int:\n",
    "        #     if L <= l and r <= R: return mx[o]\n",
    "        #     res = 0\n",
    "        #     m = (l + r) // 2\n",
    "        #     if L <= m: res = query(o * 2, l, m, L, R)\n",
    "        #     if R > m: res = max(res, query(o * 2 + 1, m + 1, r, L, R))\n",
    "        #     return res\n",
    "        # for x in nums:\n",
    "        #     if x == 1:\n",
    "        #         modify(1, 1, u, 1, 1)\n",
    "        #     else:\n",
    "        #         res = 1 + query(1, 1, u, max(x - k, 1), x - 1)\n",
    "        #         modify(1, 1, u, x, res)\n",
    "        # return mx[1]\n",
    "\n",
    "        # 2. 树状数组：基于二进制划分和倍增\n",
    "        ss = sorted(list(set(nums + [x - k for x in nums])))\n",
    "        n = len(ss) + 1 \n",
    "        t = BIT(len(ss) + 1)\n",
    "        \n",
    "        r = 1 \n",
    "        for x in nums:\n",
    "            l = bisect_left(ss, x - k)\n",
    "            x = bisect_left(ss, x)\n",
    "            xx = t.query(l, x - 1) + 1 \n",
    "            r = xx if xx > r else r \n",
    "            t.add(x, xx)\n",
    "        return r \n",
    "    \n",
    "class BIT:\n",
    "    def __init__(self, n:int):\n",
    "        self.tree = [0] * (n + n)\n",
    "        self.n = n \n",
    "    def add(self, i:int, x:int):\n",
    "        i += self.n \n",
    "        self.tree[i] = x \n",
    "        while i:\n",
    "            i >>= 1\n",
    "            self.tree[i] = max(self.tree[i * 2], self.tree[i * 2 + 1])\n",
    "    def query(self, x:int, y:int):\n",
    "        ans = 0\n",
    "        x += self.n \n",
    "        y += self.n \n",
    "        while x <= y:\n",
    "            if x % 2:\n",
    "                ans = max(ans, self.tree[x])\n",
    "                x += 1 \n",
    "            if not y % 2:\n",
    "                ans = max(ans, self.tree[y])\n",
    "                y -= 1 \n",
    "            x >>= 1 \n",
    "            y >>= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        ss = sorted(list(set(nums+[x-k for x in nums])))\n",
    "        n = len(ss) + 1\n",
    "        mx = [0] * (n+n)\n",
    "        def a(i,x):\n",
    "            i += n\n",
    "            mx[i] = x\n",
    "            while i:\n",
    "                i>>=1\n",
    "                mx[i] = max(mx[i*2],mx[i*2+1])\n",
    "        def q(x, y):\n",
    "            ans = 0\n",
    "            x += n\n",
    "            y += n\n",
    "            while x <= y:\n",
    "                if x%2:\n",
    "                    ans = max(ans,mx[x])\n",
    "                    x += 1\n",
    "                if not y%2:\n",
    "                    ans = max(ans,mx[y])\n",
    "                    y -= 1\n",
    "                x>>=1\n",
    "                y>>=1\n",
    "            return ans \n",
    "        r = 1\n",
    "        for x in nums:\n",
    "            t = bisect_left(ss,x-k)\n",
    "            x = bisect_left(ss,x) \n",
    "            xx = q(t,x-1) + 1\n",
    "            r = xx if xx > r else r\n",
    "            a(x,xx)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        t = SEGMENTTREE_ADD_MAX(max(nums),len(nums)) \n",
    "        old = defaultdict(int)\n",
    "        for x in nums:\n",
    "            q = t.query(max(0,x-k),x-1) + 1 \n",
    "            t.add(x,q-old[x]) \n",
    "            old[x] = q \n",
    "        return t.A[1]\n",
    "\n",
    "class SEGMENTTREE_ADD_MAX:\n",
    "    def __init__(self,n=10**9,q=10**5): \n",
    "        self.N = (1 << (n+3).bit_length())+1 \n",
    "        self.A = defaultdict(int) if n > q*n.bit_length() else [0]*(self.N+n+3)\n",
    "    def upd(self, l, r, x):\n",
    "        A,N = self.A,self.N \n",
    "        l += N-1\n",
    "        r += N+1\n",
    "        while l ^ r ^ 1:\n",
    "            if ~l & 1: A[l ^ 1] += x\n",
    "            if r & 1:  A[r ^ 1] += x\n",
    "            tmp = max(A[l], A[l ^ 1])\n",
    "            A[l] -= tmp;A[l ^ 1] -= tmp;A[l >> 1] += tmp\n",
    "            tmp = max(A[r], A[r ^ 1])\n",
    "            A[r] -= tmp;A[r ^ 1] -= tmp;A[r >> 1] += tmp\n",
    "            l >>= 1;r >>= 1\n",
    "        while l > 1 :\n",
    "            tmp = max(A[l], A[l ^ 1])\n",
    "            A[l] -= tmp;A[l ^ 1] -= tmp;A[l >> 1] += tmp\n",
    "            l >>= 1\n",
    "    def add(self, l,x ):\n",
    "        A,N = self.A,self.N \n",
    "        l += N \n",
    "        A[l] += x \n",
    "        while l > 1 :\n",
    "            tmp = max(A[l], A[l ^ 1])\n",
    "            A[l] -= tmp;A[l ^ 1] -= tmp;A[l >> 1] += tmp\n",
    "            l >>= 1\n",
    "    def query(self, l, r):\n",
    "        A,N = self.A,self.N \n",
    "        l += N \n",
    "        r += N \n",
    "        S = T = 0\n",
    "        if l ^ r : \n",
    "            while l ^ r ^ 1:\n",
    "                S += A[l] ; T += A[r]\n",
    "                if ~l & 1 : S = max(S,A[l^1])\n",
    "                if r & 1  : T = max(T,A[r^1])\n",
    "                l >>= 1 ; r >>= 1 \n",
    "        S = max(A[l]+S,A[r]+T) \n",
    "        while l > 1: \n",
    "            l >>= 1 ; S += A[l]\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        if (n := len(nums)) <= 3000:\n",
    "            dp = [1] * n\n",
    "            for i in range(n):\n",
    "                for j in range(i):\n",
    "                    if nums[j] < nums[i] <= nums[j] + k:\n",
    "                        dp[i] = max(dp[i], dp[j] + 1)\n",
    "            \n",
    "            return max(dp)\n",
    "        N = 1 << max(nums).bit_length()\n",
    "        A = [0] * (2*N) \n",
    "        def set(l,r,i,val):\n",
    "            if r - l == 1 : \n",
    "                A[l+r] = val \n",
    "            else : \n",
    "                m = (l + r) // 2 \n",
    "                if i < m : set(l,m,i,val) \n",
    "                else :  set(m,r,i,val) \n",
    "                A[l+r] = max(A[l+m],A[m+r]) \n",
    "        def get(l,r,L,R):\n",
    "            if L <= l and r <= R : return A[l+r] \n",
    "            if R <= l or r <= L : return 0 \n",
    "            m = (l + r ) // 2 \n",
    "            return max(get(l,m,L,R),get(m,r,L,R)) \n",
    "\n",
    "        res = 0 \n",
    "        for x in nums:\n",
    "            c = get(0,N,x-k,x) + 1\n",
    "            if c > A[x << 1 | 1 ]:\n",
    "                set(0,N,x,c)\n",
    "                res = max(res,c) \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        N = 1 << max(nums).bit_length()\n",
    "        A = [0] * (2*N) \n",
    "        def set(l,r,i,val):\n",
    "            if r - l == 1 : \n",
    "                A[l+r] = val \n",
    "            else : \n",
    "                m = (l + r) // 2 \n",
    "                if i < m : set(l,m,i,val) \n",
    "                else :  set(m,r,i,val) \n",
    "                A[l+r] = max(A[l+m],A[m+r]) \n",
    "                \n",
    "        def get(l,r,L,R):\n",
    "            if R <= l or r <= L : return 0 \n",
    "            if L <= l and r <= R : return A[l+r] \n",
    "            m = (l + r ) // 2 \n",
    "            return max(get(l,m,L,R),get(m,r,L,R)) \n",
    "\n",
    "        for x in nums:\n",
    "            c = get(0,N,x-k,x) + 1\n",
    "            if c > A[x << 1 | 1]:\n",
    "                set(0,N,x,c)\n",
    "        return A[N] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # dp[i] = max(max(dp[j]), 0) + 1, 0 < nums[i] - nums[j] <= k, 0 <= j < i\n",
    "        # pos的排序保证了nums的升序，因此可以直接popleft掉dp更小的下标\n",
    "        n = len(nums) \n",
    "        dp = [1] * n\n",
    "        dp[0] = 1\n",
    "        pos = list(range(n))\n",
    "        def cmp(x, y):\n",
    "            if nums[x] == nums[y]:\n",
    "                return 1 if x < y else -1\n",
    "            else:\n",
    "                return 1 if nums[x] > nums[y] else -1\n",
    "        pos = sorted(pos, key=functools.cmp_to_key(cmp))  # 按照nums升序排列，对于nums相同的数，下标靠后的排在前面（靠后的更优）\n",
    "        print(pos)\n",
    "\n",
    "        def search(l, r, pos):\n",
    "            if l >= r:\n",
    "                return \n",
    "            mid = (l + r) // 2\n",
    "            left, right = [], []\n",
    "            for i in pos:\n",
    "                if i > mid:\n",
    "                    right.append(i)\n",
    "                else:\n",
    "                    left.append(i)\n",
    "            search(l, mid, left)\n",
    "            # 只计算左半部分对右半部分的贡献\n",
    "            q = deque([])\n",
    "            for i in pos:  # nums[i]升序\n",
    "                if i <= mid:  # 对于左半部分，dp已计算完成，更新队列\n",
    "                    while q and dp[q[-1]] <= dp[i]:\n",
    "                        q.pop()\n",
    "                    q.append(i)\n",
    "                else:  # 对于右半部分，dp尚未计算，从队列中取值更新\n",
    "                    while q and nums[i] - nums[q[0]] > k:\n",
    "                        q.popleft()\n",
    "                    if q:\n",
    "                        dp[i] = max(dp[i], dp[q[0]] + 1)\n",
    "            search(mid + 1, r, right)\n",
    "        \n",
    "        search(0, n - 1, pos)\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # dp[i] = max(max(dp[j]), 0) + 1, 0 < nums[i] - nums[j] <= k, 0 <= j < i\n",
    "        n = len(nums) \n",
    "        dp = [1] * n\n",
    "        dp[0] = 1\n",
    "        pos = list(range(n))\n",
    "        def cmp(x, y):\n",
    "            if nums[x] == nums[y]:\n",
    "                return 1 if x < y else -1\n",
    "            else:\n",
    "                return 1 if nums[x] > nums[y] else -1\n",
    "        pos = sorted(pos, key=functools.cmp_to_key(cmp))\n",
    "        print(pos)\n",
    "\n",
    "        def search(l, r, pos):\n",
    "            if l >= r:\n",
    "                return \n",
    "            mid = (l + r) // 2\n",
    "            left, right = [], []\n",
    "            for i in pos:\n",
    "                if i > mid:\n",
    "                    right.append(i)\n",
    "                else:\n",
    "                    left.append(i)\n",
    "            search(l, mid, left)\n",
    "            q = deque([])\n",
    "            for i in pos:\n",
    "                if i <= mid:\n",
    "                    while q and dp[q[-1]] <= dp[i]:\n",
    "                        q.pop()\n",
    "                    q.append(i)\n",
    "                else:\n",
    "                    while q and nums[i] - nums[q[0]] > k:\n",
    "                        q.popleft()\n",
    "                    if q:\n",
    "                        dp[i] = max(dp[i], dp[q[0]] + 1)\n",
    "            search(mid + 1, r, right)\n",
    "        \n",
    "        search(0, n - 1, pos)\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # f[i][j] = f[i - 1][j] if j != nums[i]\n",
    "        # f[i][j] = 1 + max(f[i - 1][j']) j - k <= j' < j\n",
    "        u = max(nums)\n",
    "        st = SegmentTree()\n",
    "        for x in nums:\n",
    "            if x == 1:\n",
    "                st.update(st.root,1,u,1,1)\n",
    "            else:\n",
    "                res = 1 + st.query(st.root,1,u,max(0,x - k),x - 1)\n",
    "                st.update(st.root,1,u,x,res)\n",
    "        return st.root.val\n",
    "\n",
    "\n",
    "# 动态开点线段树，区间更新(加法），区间查询（求和）\n",
    "class Node:\n",
    "    __slots__ = ['val', 'left', 'right', 'lazy']\n",
    "\n",
    "    def __init__(self, left=None, right=None, val=0, lazy=0) -> None:\n",
    "        self.val, self.left, self.right, self.lazy = val, left, right, lazy\n",
    "\n",
    "\n",
    "# 动态开点线段树 单点更新，区间查询（求和）\n",
    "class Node:\n",
    "    __slots__ = ['val', 'left', 'right']\n",
    "\n",
    "    def __init__(self, left=None, right=None, val=0) -> None:\n",
    "        self.left, self.right, self.val = left, right, val\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 单点修改val\n",
    "    def update(self, node, s, e, index, val):\n",
    "        # 动态开点\n",
    "        if not node:\n",
    "            node = Node()\n",
    "        if s == e:\n",
    "            node.val = val\n",
    "            return node\n",
    "        mid = (s + e) >> 1\n",
    "        if index <= mid:\n",
    "            node.left = self.update(node.left, s, mid, index, val)\n",
    "        if index > mid:\n",
    "            node.right = self.update(node.right, mid + 1, e, index, val)\n",
    "        node.val = max((node.left.val if node.left else 0),(node.right.val if node.right else 0))\n",
    "        return node\n",
    "\n",
    "    def query(self, node, s, e, l, r):\n",
    "        if not node:\n",
    "            return 0\n",
    "        if l <= s and e <= r:\n",
    "            return node.val\n",
    "        mid = (s + e) >> 1\n",
    "        ans = 0\n",
    "        if l <= mid:\n",
    "            ans = max(ans,self.query(node.left, s, mid, l, r))\n",
    "        if r > mid:\n",
    "            ans = max(ans,self.query(node.right, mid + 1, e, l, r))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        m = len(nums)\n",
    "        if m == 1:\n",
    "            return 1\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        n = mx - mn + 1\n",
    "        tree= [0] * (4 * n)\n",
    "        def update(i, l, r, idx, val):\n",
    "            if idx <= l and r <= idx:\n",
    "                tree[i] = max(tree[i], val)\n",
    "                return \n",
    "            mid = (l + r) >> 1\n",
    "            if idx <= mid:\n",
    "                update(i * 2, l, mid, idx, val)\n",
    "            if idx > mid:\n",
    "                update(i * 2 + 1, mid + 1, r, idx, val)\n",
    "            tree[i] = max(tree[i * 2], tree[i * 2 + 1])\n",
    "        \n",
    "        def query(i, l, r, L, R) -> int:\n",
    "\n",
    "            if L <= l and r <= R:\n",
    "                return tree[i]\n",
    "            mid = (l + r) >> 1\n",
    "            vl = vr = 0\n",
    "            if L <= mid:\n",
    "                vl = query(i * 2, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                vr = query(i * 2 + 1, mid + 1, r, L, R)\n",
    "            return max(vl, vr)        \n",
    "        dp = [1] * m\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == mn:\n",
    "                update(1, mn, mx, x, 1)\n",
    "                continue\n",
    "            L, R = max(x - k, mn), x - 1\n",
    "            dp[i] = max(dp[i], query(1, mn, mx, L, R) + 1)\n",
    "            update(1, mn, mx, x, dp[i])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        n = len(nums)\n",
    "        self.n = n\n",
    "        self.seg = [0] * (n * 4)\n",
    "        self.build(nums, 0, 0, n - 1)\n",
    "\n",
    "    def build(self, nums: List[int], node: int, s: int, e: int):\n",
    "        if s == e:\n",
    "            self.seg[node] = nums[s]\n",
    "            return\n",
    "        m = s + (e - s) // 2\n",
    "        self.build(nums, node * 2 + 1, s, m)\n",
    "        self.build(nums, node * 2 + 2, m + 1, e)\n",
    "        self.seg[node] = max(self.seg[node * 2 + 1], self.seg[node * 2 + 2])\n",
    "\n",
    "    def update(self, index: int, val: int, node: int, s: int, e: int):\n",
    "        if s == e:\n",
    "            self.seg[node] = val\n",
    "            return\n",
    "        m = s + (e - s) // 2\n",
    "        if index <= m:\n",
    "            self.update(index, val, node * 2 + 1, s, m)\n",
    "        else:\n",
    "            self.update(index, val, node * 2 + 2, m + 1, e)\n",
    "        self.seg[node] = max(self.seg[node * 2 + 1], self.seg[node * 2 + 2])\n",
    "\n",
    "    def query(self, left: int, right: int, node: int, s: int, e: int) -> int:\n",
    "        if left == s and right == e:\n",
    "            return self.seg[node]\n",
    "        m = s + (e - s) // 2\n",
    "        if right <= m:\n",
    "            return self.query(left, right, node * 2 + 1, s, m)\n",
    "        if left > m:\n",
    "            return self.query(left, right, node * 2 + 2, m + 1, e)\n",
    "        return max(self.query(left, m, node * 2 + 1, s, m), self.query(m + 1, right, node * 2 + 2, m + 1, e))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        N = 10**5+1\n",
    "        lst = SegmentTree([0] * N)\n",
    "        dp = [1] * n\n",
    "        lst.update(nums[0], dp[0], 0, 0, N - 1)\n",
    "        hst = {nums[0]: dp[0]}\n",
    "        for i in range(1, n):\n",
    "            l, r = max(0, nums[i] - k), nums[i]-1\n",
    "            mx = lst.query(l, r, 0, 0, N - 1)\n",
    "            dp[i] = mx + 1\n",
    "            if nums[i] not in hst or hst[nums[i]] < dp[i]:\n",
    "                lst.update(nums[i], dp[i], 0, 0, N - 1)\n",
    "                hst[nums[i]] = dp[i]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = 2 ** int(math.log2(len(nums) + 1) + 1)\n",
    "        segtree = [0] * 500000\n",
    "        def update(i, x):\n",
    "            i += n\n",
    "            while i:\n",
    "                segtree[i] = max(segtree[i], x)\n",
    "                i //= 2\n",
    "        def query(i, j):\n",
    "            ans = -float(\"inf\")\n",
    "            i += n\n",
    "            j += n + 1\n",
    "            while i < j:\n",
    "                if i % 2 == 1:\n",
    "                    ans = max(ans, segtree[i])\n",
    "                    i += 1\n",
    "                if j % 2 == 1:\n",
    "                    j -= 1\n",
    "                    ans = max(ans, segtree[j])\n",
    "                    \n",
    "                i //= 2\n",
    "                j //= 2\n",
    "            return ans\n",
    "        snums = sorted(nums)\n",
    "        index = {x: i for i, x in enumerate(snums)}\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            lo = bisect.bisect_left(snums, x - k)\n",
    "            hi = bisect.bisect_right(snums, x - 1)\n",
    "            count = query(lo, hi)\n",
    "            update(index[x], count + 1)\n",
    "            ans = max(ans, count + 1)\n",
    "        return ans\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] * (n+1)\n",
    "        dp[0] = 0\n",
    "        # 0<nums[i] - nums[j]<=k\n",
    "        # nums[i]-k <= nums[j] < nums[i]\n",
    "        # 不是 j 越大越好\n",
    "        # 而是 dp 越大越好\n",
    "        vals = nums[::]\n",
    "        for num in nums:\n",
    "            vals.append(num-k)\n",
    "        vals = list(set(vals))\n",
    "        vals.sort()\n",
    "        d = {val: i for i, val in enumerate(vals)}\n",
    "        seg = SegmentTree(len(vals)+1) # 第 0 个作为空节点\n",
    "        for i, num in enumerate(nums, start=1):\n",
    "            dp[i] = 1 + seg.query(d[num-k], d[num]-1)\n",
    "            seg.update(d[num], dp[i])\n",
    "            # seg.update(d[num-k], i) # num -k 只被查询，不更新\n",
    "        # print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, n): # 初始化线段树，nums是原始数组\n",
    "        self.n = n # n是原始数组的长度\n",
    "        self.tree = [0 for _ in range(2*self.n) ] # 线段树的大小是原始数组长度的2倍\n",
    "\n",
    "    def build_tree(self, nums): # 构建线段树的函数\n",
    "        for i in range(self.n, 2 * self.n): # 填充叶子节点\n",
    "            self.tree[i] = nums[i - self.n]\n",
    "        for i in range(self.n - 1, 0, -1): # 从下往上计算非叶节点的值\n",
    "            self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1])\n",
    "\n",
    "    def update(self, index, val): # 更新元素值\n",
    "        index += self.n # 先把索引映射到线段树中对应的位置\n",
    "        self.tree[index] = val # 更新对应的值\n",
    "        while index > 0: # 不断向上更新父节点\n",
    "            left = index # 左右儿子的索引\n",
    "            right = index\n",
    "            if index % 2 == 0: # 如果当前节点是右儿子\n",
    "                right = index + 1 # 左儿子的索引为index+1\n",
    "            else: # 如果当前节点是左儿子\n",
    "                left = index - 1 # 右儿子的索引为index-1\n",
    "            self.tree[index // 2] = max(self.tree[left], self.tree[right]) # 更新父节点的值\n",
    "            index //= 2 # 更新索引为父节点的索引\n",
    "\n",
    "    def increment(self, index, x): # 累加 x\n",
    "        pre = self.query(index, index)\n",
    "        self.update(index, pre+x)\n",
    "\n",
    "    def query(self, left, right): # 查询区间最大值\n",
    "        left += self.n # 把查询区间映射到线段树中对应的位置\n",
    "        right += self.n\n",
    "        res = 0 # 初始化结果为负无穷\n",
    "        while left <= right: # 当左右端点没有相遇时\n",
    "            if left % 2 == 1: # 如果左端点是一个右儿子（即不是其父节点的左儿子）\n",
    "                res = max(res, self.tree[left]) # 取该节点的值和当前的最大值res的较大值\n",
    "                left += 1 # 向右移动左端点，跳到左儿子\n",
    "            if right % 2 == 0: # 如果右端点是一个左儿子（即不是其父节点的右儿子）\n",
    "                res = max(res, self.tree[right]) # 取该节点的值和当前的最大值res的较大值\n",
    "                right -= 1 # 向左移动右端点，跳到右儿子\n",
    "            left //= 2 # 左右端点同时向上移动到它们的父节点\n",
    "            right //= 2\n",
    "        return res # 返回查询结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        disc = sorted(set(nums))\n",
    "        id_map = dict()\n",
    "        for x in disc:\n",
    "            id_map[x - k] = bisect_left(disc, x - k)\n",
    "            id_map[x] = bisect_left(disc, x)\n",
    "\n",
    "        u = len(disc)\n",
    "        disc = None\n",
    "        h = u.bit_length()\n",
    "        tree = [0] * (u + (1 << h))\n",
    "        for x in nums:\n",
    "            p0 = id_map[x - k]\n",
    "            p = id_map[x]\n",
    "            sz = 0\n",
    "            l = (1 << h) + p0\n",
    "            r = (1 << h) + p\n",
    "            while l < r:\n",
    "                if l & 1:\n",
    "                    sz = max(sz, tree[l])\n",
    "                    l += 1\n",
    "                if r & 1:\n",
    "                    r -= 1\n",
    "                    sz = max(sz, tree[r])\n",
    "                l >>= 1\n",
    "                r >>= 1\n",
    "\n",
    "            i = (1 << h) + p\n",
    "            while i > 0:\n",
    "                tree[i] = max(tree[i], sz + 1)\n",
    "                i >>= 1\n",
    "        return tree[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        min_val = min(nums)\n",
    "        max_val = max(nums)\n",
    "        n = max_val - min_val + 1\n",
    "        f = [0 for _ in range(n * 4 + 1)]\n",
    "        \n",
    "        def modify(k, l, r, x, val):\n",
    "            if l == r:\n",
    "                f[k] = val\n",
    "                return\n",
    "            m = (l + r) >> 1\n",
    "            if x <= m:\n",
    "                modify(k << 1, l, m, x, val)\n",
    "            else:\n",
    "                modify(k << 1 | 1, m + 1, r, x, val)\n",
    "            f[k] = max(f[k << 1], f[k << 1 | 1])\n",
    "            return\n",
    "        \n",
    "        def query(k, l, r, x, y):\n",
    "            if l == x and r == y:\n",
    "                return f[k]\n",
    "            m = (l + r) >> 1\n",
    "            if y <= m:\n",
    "                return query(k << 1, l, m, x, y)\n",
    "            elif x > m:\n",
    "                return query(k << 1 | 1, m + 1, r, x, y)\n",
    "            else:\n",
    "                return max(query(k << 1, l, m, x, m), query(k << 1 | 1, m + 1, r, m + 1, y))\n",
    "            \n",
    "        for x in nums:\n",
    "            if x == min_val:\n",
    "                res = 1\n",
    "            else:\n",
    "                res = query(1, min_val, max_val, max(min_val, x - k), max(min_val, x - 1)) + 1\n",
    "            modify(1, min_val, max_val, x, res)\n",
    "        return f[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Seg:\n",
    "    def __init__(self, n, A=None):\n",
    "        self.n = n                     # 区间范围 [0,n-1]\n",
    "        self.t = [0]*n*4      # 树节点\n",
    "        self.f = defaultdict(int)      # 懒标记\n",
    "        if A:                          # 初始数组\n",
    "            self.A = A\n",
    "            self.build()\n",
    "        self.up = max\n",
    "\n",
    "    def do(self,o,l,r,x):              # 节点 o 更新 x 的具体操作\n",
    "        self.t[o] = x\n",
    "    \n",
    "    def build(self,o=1,l=0,r=None):\n",
    "        r = self.n-1 if r is None else r\n",
    "        if l==r:\n",
    "            self.t[o] = self.A[l]\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        self.build(o*2,l,m)\n",
    "        self.build(o*2+1,m+1,r)\n",
    "        self.t[o] = self.up(self.t[o*2],self.t[o*2+1])\n",
    "\n",
    "    def down(self,o,l,m,r):\n",
    "        if self.f[o] != self.f[0]:\n",
    "            self.do(o*2,l,m,self.f[o])\n",
    "            self.do(o*2+1,m+1,r,self.f[o])\n",
    "            self.f[o] = self.f[0]\n",
    "\n",
    "    def update(self,a,b,x,o=1,l=0,r=None):\n",
    "        r = self.n-1 if r is None else r\n",
    "        if a<=l and r<=b:\n",
    "            self.do(o,l,r,x)\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        self.down(o,l,m,r)\n",
    "        if a<=m:\n",
    "            self.update(a,b,x,o*2,l,m)\n",
    "        if m<b:\n",
    "            self.update(a,b,x,o*2+1,m+1,r)\n",
    "        self.t[o] = self.up(self.t[o*2],self.t[o*2+1])\n",
    "\n",
    "    def query(self,a,b,o=1,l=0,r=None):\n",
    "        r = self.n-1 if r is None else r\n",
    "        if a<=l and r<=b:\n",
    "            return self.t[o]\n",
    "        res, m = 0, (l+r)//2\n",
    "        self.down(o,l,m,r)\n",
    "        if a<=m:\n",
    "            res = self.up(res,self.query(a,b,o*2,l,m))\n",
    "        if m<b:\n",
    "            res = self.up(res,self.query(a,b,o*2+1,m+1,r))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        ma = max(nums)\n",
    "        tree = Seg(ma+1)\n",
    "        for a in nums:\n",
    "            x = 1+tree.query(max(1,a-k),a-1)\n",
    "            tree.update(a,a,x)\n",
    "        return tree.t[1]\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        nums_range = max(nums) + 1\n",
    "        mx = [0] * (4 * nums_range)\n",
    "        \n",
    "        def modify(o, l, r, i, val):\n",
    "            if l == r - 1:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            m = (l + r) >> 1\n",
    "            if i < m: modify(o << 1    , l, m, i, val)\n",
    "            else:     modify(o << 1 | 1, m, r, i, val)\n",
    "            mx[o] = max(mx[o << 1], mx[o << 1 | 1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R: return mx[o]\n",
    "            ans = 0\n",
    "            m = (l + r) >> 1\n",
    "            if L < m: ans =          query(o << 1    , l, m, L, R)\n",
    "            if m < R: ans = max(ans, query(o << 1 | 1, m, r, L, R))\n",
    "            return ans\n",
    "\n",
    "        for num in nums:\n",
    "            lis = 1 + query(1, 1, nums_range, max(num - k, 1), num)\n",
    "            modify(1, 1, nums_range, num, lis) \n",
    "        return mx[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        mx, mn = max(nums), min(nums)\n",
    "        md = mx-mn+1\n",
    "\n",
    "        nodes = [0]*(4*md)\n",
    "\n",
    "        def query(idx, l, r, s, e):\n",
    "            if r < s or l > e:\n",
    "                return 0\n",
    "            if s == l and e == r:\n",
    "                return nodes[idx]\n",
    "            mid = (l+r)//2\n",
    "            if e <= mid:\n",
    "                return query(2*idx+1, l, mid, s, e)\n",
    "            if s > mid:\n",
    "                return query(2*idx+2, mid+1, r, s, e)\n",
    "            return max(query(2*idx+1, l, mid, s, mid), query(2*idx+2, mid+1, r, mid+1, e))\n",
    "\n",
    "        def update(arr_idx, val, idx, l, r):\n",
    "            if l == r:\n",
    "                if arr_idx == l:\n",
    "                    nodes[idx] = val\n",
    "            elif l <= arr_idx <= r:\n",
    "                mid = (l+r)//2\n",
    "                if arr_idx <= mid:\n",
    "                    update(arr_idx, val, 2*idx+1, l, mid)\n",
    "                else:\n",
    "                    update(arr_idx, val, 2*idx+2, mid+1, r)\n",
    "                nodes[idx] =  max(nodes[2*idx+1], nodes[2*idx+2])\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == mn:\n",
    "                update(0, 1, 0, 0, md-1)\n",
    "                continue\n",
    "            s = max(nums[i]-k-mn, 0)\n",
    "            e = nums[i]-1-mn\n",
    "            q = query(0, 0, md-1, s, e)\n",
    "            update(nums[i]-mn, 1+q, 0, 0, md-1)\n",
    "            # print(nodes)\n",
    "\n",
    "        return max([nodes[i] for i in range(md)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # dp[i] 以 i数 结尾的LIS\n",
    "        # dp[i] = max(dp[j])  i - k <= j <= i - 1  从前面转移\n",
    "        # basecase dp[mn] = 1\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        vals = [0] * (4 * (mx - mn + 1))\n",
    "        def update(o, l, r, idx, val): # idx = val\n",
    "            if l == r:\n",
    "                vals[o] = val\n",
    "                return\n",
    "            m = l + r >> 1\n",
    "            if m >= idx: update(o * 2, l, m, idx, val)\n",
    "            else: update(o * 2 + 1, m + 1, r, idx, val)\n",
    "            vals[o] = max(vals[o * 2], vals[o * 2 + 1])\n",
    "\n",
    "        def query(o, l, r, L, R): # [L,R]\n",
    "            if L <= l and r <= R:\n",
    "                return vals[o]\n",
    "            m = l + r >> 1\n",
    "            ans = 0\n",
    "            if m >= L: ans = max(ans, query(o * 2, l, m, L, R))\n",
    "            if m + 1 <= R: ans = max(ans, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return ans\n",
    "\n",
    "        for x in nums:\n",
    "            if x == mn:\n",
    "                update(1, mn, mx, x, 1)\n",
    "            else:\n",
    "                update(1, mn, mx, x, query(1, mn, mx, max(mn, x - k), x - 1) + 1)\n",
    "        return vals[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class BIT:\n",
    "#     def __init__(self, n):\n",
    "#         self.nums = [0]*(n+1)\n",
    "#         self.n = n+1\n",
    "#     def update(self, i, val):\n",
    "#         while i < self.n:\n",
    "#             self.nums[i] = max(nums[i], val)\n",
    "#             i += i&-i\n",
    "#     def query(self, i):\n",
    "#         res = 0\n",
    "#         while i:\n",
    "#             res = max(self.nums[i], res)\n",
    "#             i &= i-1\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # 需要通过线段树维护区间最大值,离散值域 \n",
    "        n = max(nums)\n",
    "        arr = [0] * 4 * n\n",
    "        def update(i, l, r, L, R, val):# val 代表最大个数\n",
    "            if l == r:\n",
    "                arr[i] = val\n",
    "            else:\n",
    "                mid = (l+r)//2\n",
    "                if mid>=L:\n",
    "                    update(i*2, l, mid, L, R, val)\n",
    "                if mid < L:\n",
    "                    update(i*2+1, mid+1, r, L, R, val)\n",
    "                arr[i] = max(arr[i*2], arr[i*2+1])\n",
    "        def query(i, l, r, L, R):\n",
    "            if L<=l and r<=R:\n",
    "                return arr[i]\n",
    "            else:\n",
    "                mid = (l+r)//2\n",
    "                m1 = m2 = 0\n",
    "                if mid>=L:\n",
    "                    m1 = query(i*2, l, mid, L, R)\n",
    "                if mid < R:\n",
    "                    m2 = query(i*2+1, mid+1, r, L, R)\n",
    "                return max(m1, m2)\n",
    "    #线段树+dp 即nums[i]-k的最大值,树状数组维护最大值，另一个数组维护长度\n",
    "        for i, v in enumerate(nums):\n",
    "            #先更新\n",
    "            if v == 1:\n",
    "                update(1, 1, n, v,v,1)\n",
    "            else: \n",
    "                res = query(1,1,n,max(v-k,1),v-1)\n",
    "                update(1, 1, n, v,v,res+1) \n",
    "        # print(arr)怎么把后排弄掉\n",
    "        return arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        def update(o, l, r, L, R, val):\n",
    "            if L <= l and r <= R:\n",
    "                premax[o] = max(premax[o], val)\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            if m >= L: update(o * 2, l, m, L, R, val)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R, val)\n",
    "            premax[o] = max(premax[o * 2], premax[o * 2 + 1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            # 注意此处判断是否是合法区间\n",
    "            if L > R: return -inf\n",
    "            if L <= l and r <= R:\n",
    "                return premax[o]\n",
    "            res = -inf\n",
    "            m = (l + r) // 2\n",
    "            if m >= L:res = max(res, query(o * 2, l, m, L, R))\n",
    "            if m < R: res = max(res, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return res\n",
    "            \n",
    "        n = max(nums)\n",
    "        ans = -inf\n",
    "        premax = [-inf] * (n * 4)\n",
    "        for x in nums:\n",
    "            # 注意下界最小取1， 上界不包含x\n",
    "            f = max(query(1, 1, n, max(1, x - k), x - 1), 0) + 1\n",
    "            update(1, 1, n, x, x, f)\n",
    "            ans = max(ans, f)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        u = max(nums)\n",
    "        mx = [0] * (4 * u)\n",
    "\n",
    "        def modify(o: int, l: int, r: int, i: int, val: int) -> None:\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m: modify(o * 2, l, m, i, val)\n",
    "            else: modify(o * 2 + 1, m + 1, r, i, val)\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "\n",
    "        # 返回区间 [L,R] 内的最大值\n",
    "        def query(o: int, l: int, r: int, L: int, R: int) -> int:  # L 和 R 在整个递归过程中均不变，将其大写，视作常量\n",
    "            if L <= l and r <= R: return mx[o]\n",
    "            res = 0\n",
    "            m = (l + r) // 2\n",
    "            if L <= m: res = query(o * 2, l, m, L, R)\n",
    "            if R > m: res = max(res, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return res\n",
    "\n",
    "        for x in nums:\n",
    "            if x == 1:\n",
    "                modify(1, 1, u, 1, 1)\n",
    "            else:\n",
    "                res = 1 + query(1, 1, u, max(x - k, 1), x - 1)\n",
    "                modify(1, 1, u, x, res)\n",
    "        return mx[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: list[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        positions = list(range(n))\n",
    "        def f(x):\n",
    "            return (nums[x], -x)\n",
    "        positions.sort(key=f)\n",
    "        \n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "\n",
    "        def DivideAndConquer(l, r, positions):\n",
    "            nonlocal ans\n",
    "            dac = DivideAndConquer\n",
    "            if l == r:\n",
    "                return\n",
    "            m = (l + r) >> 1\n",
    "            left, right = [], []\n",
    "            for pos in positions:\n",
    "                if pos <= m:\n",
    "                    left.append(pos)\n",
    "                else:\n",
    "                    right.append(pos)\n",
    "            dac(l, m, left)\n",
    "            que = deque()\n",
    "            for pos in positions:\n",
    "                if pos <= m:\n",
    "                    while que and dp[pos] >= dp[que[-1]]:\n",
    "                        que.pop()\n",
    "                    que.append(pos)\n",
    "                else:\n",
    "                    while que and nums[que[0]] < nums[pos] - k:\n",
    "                        que.popleft()\n",
    "                    if que: dp[pos] = max(dp[pos], dp[que[0]] + 1)\n",
    "                    ans = max(ans, dp[pos])\n",
    "            dac(m + 1, r, right)\n",
    "\n",
    "        DivideAndConquer(0, n - 1, positions)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'val', 'start', 'end', 'left', 'right'\n",
    "    \n",
    "    def __init__(self, val=0, start=0, end=1, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        mi, mx = min(nums), max(nums)\n",
    "        dp = [0] * (mx - mi + 1)\n",
    "        n = len(dp)\n",
    "        def build_tree(lo, hi):\n",
    "            if lo == hi - 1:\n",
    "                return Node(dp[lo], lo, hi)\n",
    "            mid = (lo + hi) // 2\n",
    "            left = build_tree(lo, mid)\n",
    "            right = build_tree(mid, hi)\n",
    "            return Node(max(left.val, right.val), lo, hi, left, right)\n",
    "        root = build_tree(0, n)\n",
    "        def query(node, lo, hi):\n",
    "            if lo == hi: return 0\n",
    "            if lo == node.start and hi == node.end:\n",
    "                return node.val\n",
    "            mid = (node.start + node.end) // 2\n",
    "            if hi <= mid:\n",
    "                return query(node.left, lo, hi)\n",
    "            if lo >= mid:\n",
    "                return query(node.right, lo, hi)\n",
    "            return max(query(node.left, lo, mid), query(node.right, mid, hi))\n",
    "        def update(node, i, val):\n",
    "            if node.start == i == node.end - 1:\n",
    "                dp[i] = node.val = val\n",
    "                return\n",
    "            mid = (node.start + node.end) // 2\n",
    "            if i < mid:\n",
    "                update(node.left, i, val)\n",
    "            else:\n",
    "                update(node.right, i, val)\n",
    "            node.val = max(node.left.val, node.right.val)\n",
    "        for x in nums:\n",
    "            x -= mi\n",
    "            res = 1 + query(root, max(0, x - k), x)\n",
    "            if res > dp[x]:\n",
    "                update(root, x, res)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class FenwickTree:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.max_tree = [0]*(n + 1)\n",
    "        self.arr = [0]*(n+1)\n",
    "\n",
    "    def update(self, idx, val):\n",
    "        index=idx\n",
    "        self.arr[index]=val\n",
    "        while idx<=self.n:\n",
    "            if self.arr[index]>self.max_tree[idx]:\n",
    "                self.max_tree[idx]=self.arr[index]\n",
    "            idx+=idx&(-idx)\n",
    "\n",
    "    def query_max(self, x, y):\n",
    "        ans=0\n",
    "        while x<=y:\n",
    "            if self.arr[y]>ans:\n",
    "                ans=self.arr[y]\n",
    "            y-=1\n",
    "            while y-(-y&y)>=x:\n",
    "                if self.max_tree[y]>ans:\n",
    "                    ans=self.max_tree[y]\n",
    "                y-=-y&y\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        arr=set(nums)\n",
    "        arr=sorted(list(arr)+[-10**9,10**9]+[i-1 for i in arr]+[i-k for i in arr])\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        res=0\n",
    "        bit=FenwickTree(len(arr)+5)\n",
    "        for num in nums:\n",
    "            left = d[num-k]\n",
    "            right = d[num-1]\n",
    "            v=bit.query_max(left, right) + 1\n",
    "            if v>res: \n",
    "                res = v\n",
    "            bit.update(d[num],v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZKW:\n",
    "    # n = 1\n",
    "    # size = 1\n",
    "    # log = 2\n",
    "    # d = [0]\n",
    "    # op = None\n",
    "    # e = 10 ** 15\n",
    "    \"\"\"自低向上非递归写法线段树，0_indexed\n",
    "    tmx = ZKW(pre, max, -2 ** 61)\n",
    "    \"\"\"\n",
    "    __slots__ = ('n', 'op', 'e', 'log', 'size', 'd')\n",
    "\n",
    "    def __init__(self, n, OP, E):\n",
    "        \"\"\"\n",
    "        OP: 操作:max,min,sum\n",
    "        E: 每个元素默认值\n",
    "        \"\"\"\n",
    "        self.n = n\n",
    "        self.op = OP\n",
    "        self.e = E\n",
    "        self.log = (self.n - 1).bit_length()\n",
    "        self.size = 1 << self.log\n",
    "        self.d = [E for i in range(2 * self.size)]\n",
    "\n",
    "    def set(self, p, x):\n",
    "        # assert 0 <= p and p < self.n\n",
    "        update = self.update\n",
    "        p += self.size\n",
    "        if self.d[p]<x:\n",
    "            self.d[p] = x\n",
    "            for i in range(1, self.log + 1):\n",
    "                update(p >> i)\n",
    "\n",
    "    def query(self, l, r):  # [l,r)左闭右开\n",
    "        # assert 0 <= l and l <= r and r <= self.n\n",
    "        sml, smr, op, d = self.e, self.e, self.op, self.d\n",
    "        l += self.size\n",
    "        r += self.size\n",
    "        while l < r:\n",
    "            if l & 1:\n",
    "                sml = op(sml, d[l])\n",
    "                l += 1\n",
    "            if r & 1:\n",
    "                smr = op(d[r - 1], smr)\n",
    "                r -= 1\n",
    "            l >>= 1\n",
    "            r >>= 1\n",
    "        return self.op(sml, smr)\n",
    "\n",
    "    def update(self, k):\n",
    "        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        arr=set(nums)\n",
    "        arr=set(nums+[-10**9,10**9]+[i-1 for i in arr]+[i-k for i in arr])\n",
    "        arr=sorted(arr)\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        n=max(nums)\n",
    "        seg=ZKW(len(d)*4,max,0)\n",
    "        res=1\n",
    "        for i in nums:\n",
    "            q=0 if i==1 else seg.query(d[i-k],d[i-1]+1)\n",
    "            res=max(res,q+1)\n",
    "            seg.set(d[i],q+1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: list[int], k: int) -> int:\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        # 离散化\n",
    "        uniques = set(nums)\n",
    "        rank_map = {v:i+1 for i,v in enumerate(sorted(uniques))}\n",
    "        \n",
    "        tree = [[0,0] for i in range(len(rank_map)+1)]\n",
    "        \n",
    "        def update(i, val, num):  # 更新最大值\n",
    "            while i < len(tree):\n",
    "                \n",
    "                if tree[i][0] < val:\n",
    "                    tree[i][1] = num\n",
    "                    tree[i][0] = val\n",
    "                elif tree[i][0] == val:\n",
    "                    tree[i][1] = max(tree[i][1], num)\n",
    "                i += lowbit(i)\n",
    "        \n",
    "        def query(i,num,k):       # 查询最大值\n",
    "            ans = 0\n",
    "            while i > 0:\n",
    "                if num - tree[i][1] <=k:\n",
    "                    ans = max(ans, tree[i][0])\n",
    "                \n",
    "                i -= lowbit(i)\n",
    "            return ans\n",
    "        \n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            rank = rank_map[num]\n",
    "            val = query(rank-1,num,k)     # 查询比nums[i]严格小的LIS长度\n",
    "            \n",
    "            update(rank, val+1,num)     # 更新最大值：<nums[i]的元素数目+1\n",
    "            ans = max(ans, val+1)   # 更新答案\n",
    "            \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: list[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        positions = list(range(n))\n",
    "        def f(x):\n",
    "            return (nums[x], -x)\n",
    "        positions.sort(key=f)\n",
    "        \n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "\n",
    "        def DivideAndConquer(l, r, positions):\n",
    "            nonlocal ans\n",
    "            dac = DivideAndConquer\n",
    "            if l == r:\n",
    "                return\n",
    "            m = (l + r) >> 1\n",
    "            left, right = [], []\n",
    "            for pos in positions:\n",
    "                if pos <= m:\n",
    "                    left.append(pos)\n",
    "                else:\n",
    "                    right.append(pos)\n",
    "            dac(l, m, left)\n",
    "            \n",
    "            que = deque()\n",
    "            for pos in positions:\n",
    "                if pos <= m:\n",
    "                    while que and dp[pos] >= dp[que[-1]]:\n",
    "                        que.pop()\n",
    "                    que.append(pos)\n",
    "                else:\n",
    "                    while que and nums[que[0]] < nums[pos] - k:\n",
    "                        que.popleft()\n",
    "                    if que: dp[pos] = max(dp[pos], dp[que[0]] + 1)\n",
    "                    ans = max(ans, dp[pos])\n",
    "            \n",
    "            dac(m + 1, r, right)\n",
    "\n",
    "        DivideAndConquer(0, n - 1, positions)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        p = list(range(n))\n",
    "        # 对索引排序，若数值相等，则位置靠后的排在前\n",
    "        p.sort(key=lambda x: (nums[x], -x))\n",
    "        def DFS(L, R, p):\n",
    "            if L >= R: \n",
    "                return\n",
    "            M = (L + R) // 2\n",
    "            q = [[], []]\n",
    "            for i in p:\n",
    "                q[i > M].append(i)\n",
    "            DFS(L, M, q[0])\n",
    "            dq = deque()\n",
    "            for i in p:\n",
    "                if i <= M:\n",
    "                    # dq中维护一系列下标，使得对应的dp值是单调递减的\n",
    "                    while dq and dp[dq[-1]] <= dp[i]:\n",
    "                        dq.pop()\n",
    "                    dq.append(i)\n",
    "                else:\n",
    "                    # 在dp的值单调递减的序列中找到一个最大的dp[j]满足nums[j]+k>=nums[i]，更新dp[i]\n",
    "                    while dq and nums[dq[0]] < nums[i] - k:\n",
    "                        dq.popleft()\n",
    "                    if dq:\n",
    "                        dp[i] = max(dp[i], dp[dq[0]] + 1)\n",
    "            DFS(M + 1, R, q[1])\n",
    "\n",
    "        DFS(0, n - 1, p)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        u = max(nums)\n",
    "        mx = [0] * (4 * u)\n",
    "        \n",
    "        def modify(o, l, r, i, val):\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m: modify(o*2, l, m, i, val)\n",
    "            else: modify(o*2+1, m+1, r, i, val)\n",
    "            mx[o] = mx[o*2] if  mx[o*2] > mx[o*2+1] else mx[o*2+1]\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return mx[o]\n",
    "            m = (l + r) // 2\n",
    "            res = 0\n",
    "            if L <= m: \n",
    "                res = query(o*2, l, m, L, R)\n",
    "            if R > m: \n",
    "                b = query(o*2+1, m+1, r, L, R)\n",
    "                if b > res:\n",
    "                    res = b\n",
    "            return res\n",
    "\n",
    "        for x in nums:\n",
    "            if x == 1:\n",
    "                modify(1, 1, u, 1, 1)\n",
    "            else:\n",
    "                res = 1 + query(1, 1, u, max(1, x-k), x-1)\n",
    "                modify(1, 1, u, x, res)\n",
    "        print(mx)\n",
    "        return mx[1]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # mn, mx = min(nums), max(nums)\n",
    "\n",
    "        # d[i][j] 前i个元素以j结尾的LIS\n",
    "        # if nums[i]!=j: dp[i-1][j]\n",
    "        # else: max(dp[i-1][j'])+1  j-k<=j'<j\n",
    "        # i:[0,n] j:[mn,mx]\n",
    "        # f[j] = max(f[j']+1) j-k<=j'<j x==j # 倒序\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     if nums[i] != j:\n",
    "        #         return dfs(i - 1, j)\n",
    "        #     ans = 1\n",
    "        #     for x in range(max(1, j - k), j):\n",
    "        #         if (sub := dfs(i - 1, x) + 1) > ans:\n",
    "        #             ans = sub\n",
    "        #     return ans\n",
    "\n",
    "        # return max(dfs(n - 1, i) for i in range(mn, mx + 1))\n",
    "\n",
    "        # f = [[0] * (mx + 1) for _ in range(n + 1)]\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     for j in range(mn, mx + 1):\n",
    "        #         if num != j:\n",
    "        #             f[i + 1][j] = f[i][j]\n",
    "        #         else:\n",
    "        #             f[i + 1][j] = 1\n",
    "        #             for x in range(max(1, j - k), j):\n",
    "        #                 if f[i][x] + 1 > f[i + 1][j]:\n",
    "        #                     f[i + 1][j] = f[i][x] + 1\n",
    "        # return max(f[n])\n",
    "\n",
    "        # f = [[0] * (mx + 1) for _ in range(2)]\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     for j in range(mn, mx + 1):\n",
    "        #         if num != j:\n",
    "        #             f[i + 1 & 1][j] = f[i & 1][j]\n",
    "        #         else:\n",
    "        #             f[i + 1 & 1][j] = 1\n",
    "        #             for x in range(max(1, j - k), j):\n",
    "        #                 if f[i & 1][x] + 1 > f[i + 1 & 1][j]:\n",
    "        #                     f[i + 1 & 1][j] = f[i & 1][x] + 1\n",
    "        # return max(f[n & 1])\n",
    "\n",
    "        # f = [0] * (mx + 1)\n",
    "        # for num in nums:\n",
    "        #     for j in range(mx, mn - 1, -1):\n",
    "        #         if num == j:\n",
    "        #             f[j] = 1\n",
    "        #             for x in range(max(1, j - k), j): # 区间最大值\n",
    "        #                 if f[x] + 1 > f[j]:\n",
    "        #                     f[j] = f[x] + 1\n",
    "        # return max(f)\n",
    "\n",
    "        # f = [0] * (mx + 1)\n",
    "        # for num in nums:\n",
    "        #     for j in range(mx, mn - 1, -1):\n",
    "        #         if num == j:\n",
    "        #             f[j] = 1\n",
    "        #             if j - 1 >= (left:=max(1, j - k)):\n",
    "        #                 f[j] = max(f[left:j]) + 1\n",
    "        # return max(f)\n",
    "\n",
    "        # f = [0] * (mx + 1)\n",
    "        # for num in nums:\n",
    "        #     for j in range(mx, mn - 1, -1):\n",
    "        #         if num == j:\n",
    "        #             f[j] = 1\n",
    "        #             if j - 1 >= (left:=max(1, j - k)):\n",
    "        #                 f[j] = max(f[left:j]) + 1\n",
    "        # return max(f)\n",
    "\n",
    "        # f = [0] * (mx + 1)\n",
    "        # for x in nums:\n",
    "        #     f[x] = 1\n",
    "        #     if x - 1 >= (left:=max(1, x - k)):\n",
    "        #         f[x] = max(f[left: x]) + 1\n",
    "        # return max(f)\n",
    "\n",
    "        u = max(nums) + 1\n",
    "        mxo = [0] * (2 << u.bit_length())\n",
    "        lazy = [None] * (2 << u.bit_length())\n",
    "\n",
    "        def pushdown(o):\n",
    "            if lazy[o] is not None:\n",
    "                mxo[o * 2] = mxo[o * 2 + 1] = lazy[o * 2] = lazy[o * 2 + 1] = lazy[o]\n",
    "                lazy[o] = None\n",
    "        \n",
    "        def update(o, l ,r, idx, val):\n",
    "            if l == r:\n",
    "                mxo[o] = val\n",
    "                return\n",
    "            pushdown(o)\n",
    "            m = l + r >> 1\n",
    "            if m >= idx:\n",
    "                update(o * 2, l, m, idx, val)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, idx, val)\n",
    "            mxo[o] = max(mxo[o * 2], mxo[o * 2 + 1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return mxo[o]\n",
    "            pushdown(o)\n",
    "            m = l + r >> 1\n",
    "            ans = 0\n",
    "            if m >= L:\n",
    "                ans = query(o * 2, l, m, L, R)\n",
    "            if m + 1 <= R:\n",
    "                ans = max(ans, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return ans\n",
    "\n",
    "        # for x in nums:\n",
    "        #     if x - 1 >= (left:=max(1, x - k)):\n",
    "        #         update(1, 0, u - 1, x, query(1, 0, u - 1, left, x - 1) + 1)\n",
    "        #     else:\n",
    "        #         update(1, 0, u - 1, x, 1)\n",
    "        # return mxo[1]\n",
    "\n",
    "        for x in nums:\n",
    "            if x != 1:\n",
    "                update(1, 0, u - 1, x, query(1, 0, u - 1, max(1, x - k), x - 1) + 1)\n",
    "            else:\n",
    "                update(1, 0, u - 1, x, 1)\n",
    "        return mxo[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        def update(id_tree,left,right,index,val):\n",
    "            if left==right==index:\n",
    "                sg_tree[id_tree]=max(sg_tree[id_tree],val)\n",
    "                return sg_tree[id_tree]\n",
    "            mid=(left+right)//2\n",
    "            if index<=mid:\n",
    "                sg_tree[id_tree]=max(update(2*id_tree,left,mid,index,val),sg_tree[2*id_tree+1])\n",
    "            else:\n",
    "                sg_tree[id_tree]=max(sg_tree[2*id_tree],update(2*id_tree+1,mid+1,right,index,val))\n",
    "            return sg_tree[id_tree]\n",
    "        def query(id_tree,left,right,start,end):\n",
    "            if left==start and right==end:\n",
    "                return sg_tree[id_tree]\n",
    "            mid=(left+right)//2\n",
    "            if end<=mid:\n",
    "                return query(2*id_tree,left,mid,start,end)\n",
    "            if mid<start:\n",
    "                return query(2*id_tree+1,mid+1,right,start,end)\n",
    "            return max(query(2*id_tree,left,mid,start,mid),query(2*id_tree+1,mid+1,right,mid+1,end))\n",
    "        arr=set(nums+[-10**9,10**9]+[i-1 for i in nums]+[i-k for i in nums])\n",
    "        arr=sorted(arr)\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        n=len(d)\n",
    "        #print(arr)\n",
    "        sg_tree=[0]*(4*n)\n",
    "        res=1\n",
    "        for i in nums:\n",
    "            q=0 if i==1 else query(1,1,n,d[i-k],d[i-1])\n",
    "\n",
    "            res=max(res,q+1)\n",
    "            update(1,1,n,d[i],q+1)\n",
    "        #print(sg_tree)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tree = {}\n",
    "        \n",
    "    def build_tree(self,left, right):\n",
    "        if left > right:\n",
    "            return\n",
    "        root = left * 100100 + right\n",
    "        self.tree[root] = -1\n",
    "        if left == right:\n",
    "            return\n",
    "        mid = (left+right) // 2\n",
    "        self.build_tree(left, mid)\n",
    "        self.build_tree(mid+1,right)\n",
    "    \n",
    "    def find_max(self,left,right, L, R):\n",
    "        mid = (left+right) // 2\n",
    "        root = left * 100100 + right\n",
    "        if L <= left and right<=R:\n",
    "            return self.tree[root]\n",
    "        \n",
    "        t1 = 0\n",
    "        t2 = 0\n",
    "        if L <= mid:\n",
    "            t1 = self.find_max(left,mid,L,R)\n",
    "        if R > mid:\n",
    "            t2 = self.find_max(mid+1,right,L,R)\n",
    "        return max(t1,t2)\n",
    "    \n",
    "    def insert(self,left,right,pos,val):\n",
    "        if left > right:\n",
    "            return\n",
    "        root = left * 100100 + right\n",
    "        self.tree[root] = max(self.tree[root],val)\n",
    "        if left == right:\n",
    "            return\n",
    "        mid = (left+right) // 2\n",
    "        if pos <= mid:\n",
    "            self.insert(left,mid,pos,val)\n",
    "        else:\n",
    "            self.insert(mid+1,right,pos,val)\n",
    "        \n",
    "    \n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        self.build_tree(0,100001)\n",
    "        n = len(nums)\n",
    "        ret = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ret[i] = self.find_max(0,100001,max(nums[i]-k,0),max(nums[i]-1,0)) + 1\n",
    "            \n",
    "            self.insert(0,100001,nums[i],ret[i])\n",
    "        return max(ret)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "一题多解：找一找「方法二」\n",
    "\n",
    "对于上升子序列  O(nlogn)   300 题\n",
    "\n",
    "1. 二分  理解方式：二分的位置如果在 d 数组中间的话，那么 d[i] = num\n",
    "                 增大了 d 数组变长的潜力\n",
    "2. 线段树优化\n",
    "\n",
    "\n",
    "3. 从 O(n^2) 出发\n",
    "\n",
    "定义 f[i][j] 表示从 nums 的前 i 个数中选择以元素 j 结尾的上升子序列的最长长度\n",
    "\n",
    "- 如果 j == nums[i]，f[j] = 1 + max(f[j'])   j' < j\n",
    "\n",
    "等号左侧：单点修改\n",
    "等号右侧：区间求 max\n",
    "=> 线段树\n",
    "\n",
    "答案为 max(f[n-1]) => 线段树根节点的值\n",
    "\n",
    "4. 学习线段树，把握住两个事实\n",
    "    1. 每个区间都可以拆分成 O(log n) 个子区间\n",
    "    2. 只需要 O(n) 个子区间，就能拼成任意区间\n",
    "5. 补充：懒惰思想：如果当前线段树节点对应的区间被查询区间完整包含，那么不需要继续递归查询，对于更新操作\n",
    "    需要记录一下更新的内容 lazy tag，在这里打住，后续的某个更新操作，如果需要继续递归的话，那么就带着\n",
    "     lazy tag 往下继续递归，就好比接着之前的计算一样。\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        u = max(nums) + 1\n",
    "        mx = [0] * (3 * u)\n",
    "\n",
    "        # 假设维护的是数组 a\n",
    "        # 修改 a[i] = val\n",
    "        def modify(o, l, r, i, val):\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            if i <= m: modify(o * 2, l, m, i, val)\n",
    "            else: modify(o * 2 + 1, m + 1, r, i, val)\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "        \n",
    "        # 查询 max(a[L:R+1])  [L,R]\n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and r <= R:\n",
    "                return mx[o]\n",
    "            res = 0\n",
    "            m = (l + r) // 2\n",
    "            if L <= m: res = query(o * 2, l, m, L, R)\n",
    "            if R > m: res = max(res, query(o * 2 + 1, m + 1, r, L, R))\n",
    "            return res\n",
    "        \n",
    "        for x in nums:\n",
    "            x += 1\n",
    "            res = 1 + query(1, 1, u, max(x - k, 1), x - 1)\n",
    "            modify(1, 1, u, x, res)\n",
    "        return mx[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    __slots__ = 'start', 'end', 'mid', 'val', 'left', 'right', 'lazy'\n",
    "    def __init__(self, start, end, val=0) -> None:\n",
    "        self.start = start \n",
    "        self.end = end \n",
    "        self.mid = math.floor((self.start + self.end) / 2)\n",
    "        self.val = val \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.lazy = 0 \n",
    "        \n",
    "    def update(self, l, r, val):\n",
    "        if l <= self.start and self.end <= r:\n",
    "            self.val = val\n",
    "            self.lazy = val \n",
    "            return \n",
    "     \n",
    "       \n",
    "        self.pushdown()\n",
    "        if l <= self.mid:\n",
    "            self.left.update(l, r, val)\n",
    "        if r >= self.mid + 1:\n",
    "            self.right.update(l, r, val)\n",
    "        self.pushup()\n",
    "       \n",
    "    def query(self, l, r):\n",
    "        if r < l:\n",
    "            return 0\n",
    "        if l <= self.start and self.end <= r:\n",
    "            return self.val\n",
    "       \n",
    "        self.pushdown()\n",
    "        ans = 0 \n",
    "        if l <= self.mid:\n",
    "            ans = max(ans, self.left.query(l, r))\n",
    "        if r >= self.mid + 1:\n",
    "            ans = max(ans, self.right.query(l, r))\n",
    "        return ans \n",
    "        \n",
    "    def pushup(self):\n",
    "        self.val = max(self.left.val, self.right.val)\n",
    "        \n",
    "    def pushdown(self):\n",
    "      \n",
    "        if not self.left:\n",
    "            self.left = SegTree(self.start, self.mid)\n",
    "        if not self.right:\n",
    "            self.right = SegTree(self.mid+1, self.end)\n",
    "        if self.lazy == 0:\n",
    "            return \n",
    "        \n",
    "        self.left.lazy = self.lazy \n",
    "        self.left.val = (self.mid-self.start+1)*self.lazy \n",
    "        self.right.lazy = self.lazy \n",
    "        self.right.val = (self.end-self.mid)*self.lazy \n",
    "        self.lazy = 0\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums, k) -> int:\n",
    "        mx = max(nums)\n",
    "        seg = SegTree(1, mx, 0)\n",
    "        for i, x in enumerate(nums):\n",
    "            s = seg.query(max(1, x-k), x-1)\n",
    "            seg.update(x, x, s+1)\n",
    "\n",
    "        return seg.query(1, mx+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=0, add=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.add = add\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    \n",
    "def push_down(node):\n",
    "    if not node.left:\n",
    "        node.left = Node()\n",
    "    if not node.right:\n",
    "        node.right = Node()\n",
    "    if node.add == 0:\n",
    "        return\n",
    "    node.left.val += node.add\n",
    "    node.right.val += node.add\n",
    "    node.left.add += node.add\n",
    "    node.right.add += node.add\n",
    "    node.add = 0\n",
    "\n",
    "def push_up(node):\n",
    "    node.val = max(node.left.val, node.right.val)\n",
    "\n",
    "def update(node, start, end, l, r, val):\n",
    "    if l <= start and end <= r :\n",
    "        node.val = val\n",
    "        node.add = val\n",
    "        return\n",
    "    mid = (start + end) // 2\n",
    "    push_down(node)\n",
    "    if l <= mid:\n",
    "        update(node.left, start, mid, l, r, val)\n",
    "    if r > mid:\n",
    "        update(node.right, mid+1, end, l, r, val)\n",
    "    push_up(node)\n",
    "\n",
    "def query(node, start, end, l, r):\n",
    "    if l <= start and end <= r:\n",
    "        return node.val\n",
    "    mid = (start + end) // 2\n",
    "    push_down(node)\n",
    "    ans = 0\n",
    "    if l <= mid:\n",
    "        ans = query(node.left, start, mid, l, r)\n",
    "    if r > mid:\n",
    "        ans = max(ans, query(node.right, mid+1, end, l, r))\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        head = Node()\n",
    "        N = 10 ** 5\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cnt = query(head, 0, N, max(0, nums[i] - k), nums[i]-1) + 1\n",
    "            update(head, 0, N, nums[i], nums[i], cnt)\n",
    "            ans = max(ans, cnt)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self) -> None:\n",
    "        # ls 和 rs 分别代表当前区间的左右子节点\n",
    "        self.ls = self.rs = None\n",
    "        # val 代表当前区间的维护值 add 为懒标记\n",
    "        self.val = self.add = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    @staticmethod\n",
    "    def update(node: Node, lc: int, rc: int, l: int, r: int, v: int) -> None:\n",
    "        if l <= lc and rc <= r:\n",
    "            node.add = v\n",
    "            node.val = v\n",
    "            return\n",
    "        SegmentTree.pushdown(node)\n",
    "        mid = (lc + rc) >> 1\n",
    "        if l <= mid:\n",
    "            SegmentTree.update(node.ls, lc, mid, l, r, v)\n",
    "        if r > mid:\n",
    "            SegmentTree.update(node.rs, mid + 1, rc, l, r, v)\n",
    "        SegmentTree.pushup(node)\n",
    " \n",
    "    @staticmethod\n",
    "    def query(node: Node, lc: int, rc: int, l: int, r: int) -> int:\n",
    "        if l <= lc and rc <= r:\n",
    "            return node.val\n",
    "        # 先确保所有关联的懒标记下沉下去\n",
    "        SegmentTree.pushdown(node)\n",
    "        mid, ans = (lc + rc) >> 1, 0\n",
    "        if l <= mid:\n",
    "            ans = SegmentTree.query(node.ls, lc, mid, l, r)\n",
    "        if r > mid:\n",
    "            # 同样为不同题目中的更新方式\n",
    "            ans = max(ans, SegmentTree.query(node.rs, mid + 1, rc, l, r))\n",
    "        return ans\n",
    "    \n",
    "    @staticmethod\n",
    "    def pushdown(node: Node) -> None:\n",
    "        # 懒标记, 在需要的时候才开拓节点和赋值\n",
    "        if node.ls is None:\n",
    "            node.ls = Node()\n",
    "        if node.rs is None:\n",
    "            node.rs = Node()\n",
    "        if not node.add:\n",
    "            return\n",
    "        node.ls.add, node.rs.add, node.ls.val, node.rs.val = [node.add] * 4\n",
    "        node.add = 0\n",
    "    \n",
    "    @staticmethod\n",
    "    def pushup(node: Node) -> None:\n",
    "        # 动态更新方式：此处为最大值\n",
    "        node.val = max(node.ls.val, node.rs.val)\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        mx = max(nums)\n",
    "        trie = SegmentTree()\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            left, right = max(1, nums[i]-k), nums[i]-1\n",
    "            s = trie.query(trie.root, 0, mx, left,right)\n",
    "            ans = max(ans, s+1)\n",
    "            trie.update(trie.root, 0, mx, nums[i], nums[i], s+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ZKW:\n",
    "    # n = 1\n",
    "    # size = 1\n",
    "    # log = 2\n",
    "    # d = [0]\n",
    "    # op = None\n",
    "    # e = 10 ** 15\n",
    "    \"\"\"自低向上非递归写法线段树，0_indexed\n",
    "    tmx = ZKW(pre, max, -2 ** 61)\n",
    "    \"\"\"\n",
    "    __slots__ = ('n', 'op', 'e', 'log', 'size', 'd')\n",
    "\n",
    "    def __init__(self, n, OP, E):\n",
    "        \"\"\"\n",
    "        OP: 操作:max,min,sum\n",
    "        E: 每个元素默认值\n",
    "        \"\"\"\n",
    "        self.n = n\n",
    "        self.op = OP\n",
    "        self.e = E\n",
    "        self.log = (self.n - 1).bit_length()\n",
    "        self.size = 1 << self.log\n",
    "        self.d = [E for i in range(2 * self.size)]\n",
    "\n",
    "    def set(self, p, x):\n",
    "        # assert 0 <= p and p < self.n\n",
    "        update = self.update\n",
    "        p += self.size\n",
    "        if self.d[p]<x:\n",
    "            self.d[p] = x\n",
    "            for i in range(1, self.log + 1):\n",
    "                update(p >> i)\n",
    "\n",
    "    def query(self, l, r):  # [l,r)左闭右开\n",
    "        # assert 0 <= l and l <= r and r <= self.n\n",
    "        sml, smr, op, d = self.e, self.e, self.op, self.d\n",
    "        l += self.size\n",
    "        r += self.size\n",
    "        while l < r:\n",
    "            if l & 1:\n",
    "                sml = op(sml, d[l])\n",
    "                l += 1\n",
    "            if r & 1:\n",
    "                smr = op(d[r - 1], smr)\n",
    "                r -= 1\n",
    "            l >>= 1\n",
    "            r >>= 1\n",
    "        return self.op(sml, smr)\n",
    "\n",
    "    def update(self, k):\n",
    "        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        arr=set(nums)\n",
    "        arr=sorted(list(arr)+[-10**9,10**9]+[i-1 for i in arr]+[i-k for i in arr])\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        n=max(nums)\n",
    "        seg=ZKW(len(d)*4,max,0)\n",
    "        res=1\n",
    "        for i in nums:\n",
    "            q=0 if i==1 else seg.query(d[i-k],d[i-1]+1)\n",
    "            res=max(res,q+1)\n",
    "            seg.set(d[i],q+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def query(self, l, r, L, R):\n",
    "        if R < L:\n",
    "            return 0\n",
    "        if L <= l and r <= R:\n",
    "            return self.val\n",
    "        mid = (l + r) >> 1\n",
    "        mx = 0\n",
    "        self.build()\n",
    "        if L <= mid:\n",
    "            mx = self.left.query(l, mid, L, R)\n",
    "        if R > mid:\n",
    "            mx = max(mx, self.right.query(mid + 1, r, L, R))\n",
    "        return mx\n",
    "    def update(self, l, r, idx, v):\n",
    "        if l == r:\n",
    "            self.val = v\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build()\n",
    "        if idx <= mid:\n",
    "            self.left.update(l, mid, idx, v)\n",
    "        else:\n",
    "            self.right.update(mid + 1, r, idx, v)\n",
    "        self.val = max(self.left.val, self.right.val)\n",
    "\n",
    "    def build(self):\n",
    "        if not self.left:\n",
    "            self.left = Node()\n",
    "        if not self.right:\n",
    "            self.right = Node()\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        mx = max(nums)\n",
    "        root = Node()\n",
    "        for num in nums:\n",
    "            L, R = max(1, num - k), num - 1\n",
    "            val = root.query(1, mx, L, R) + 1\n",
    "            root.update(1, mx, num, val)\n",
    "        return root.val\n",
    "\n",
    "    def lengthOfLIS1(self, nums: List[int], k: int) -> int:\n",
    "        mx = max(nums)\n",
    "        root = [0] * (4 * mx)\n",
    "        def query(u: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            if R < L:\n",
    "                return 0\n",
    "            if L <= l and r <= R:\n",
    "                return root[u]\n",
    "            mid = (l + r) >> 1\n",
    "            m = 0\n",
    "            if L <= mid:\n",
    "                m = query(u * 2, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                m = max(m, query(u * 2 + 1, mid + 1, r, L, R))\n",
    "            return m\n",
    "        def update(u: int, l: int, r: int, idx: int, val: int) -> None:\n",
    "            if l == r:\n",
    "                root[u] = val\n",
    "                return\n",
    "            mid = (l + r) >> 1\n",
    "            if idx <= mid:\n",
    "                update(u * 2, l, mid, idx, val)\n",
    "            else:\n",
    "                update(u * 2 + 1, mid + 1, r, idx, val)\n",
    "            root[u] = max(root[u * 2], root[u * 2 + 1])\n",
    "        \n",
    "        for num in nums:\n",
    "            L, R = max(1, num - k), num - 1\n",
    "            val = query(1, 1, mx, L, R) + 1\n",
    "            update(1, 1, mx, num, val)\n",
    "        return root[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = 0\n",
    "        self.add = 0\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.N = int(1e5)\n",
    "        self.root = Node()\n",
    "    def update(self, node, lc, rc, l,r,v):\n",
    "        if l<=lc and rc<=r:\n",
    "            node.val = v\n",
    "            node.add = v\n",
    "            return \n",
    "        self.pushdown(node)\n",
    "        m = (lc+rc)>>1\n",
    "        if l<=m:\n",
    "            self.update(node.left, lc, m, l,r,v)\n",
    "        if r>m:\n",
    "            self.update(node.right, m+1, rc, l,r,v)\n",
    "        self.pushup(node)\n",
    "    def query(self, node, lc, rc, l,r):\n",
    "        if l<=lc and rc<=r:\n",
    "            return node.val\n",
    "        self.pushdown(node)\n",
    "        m = (lc+rc)>>1\n",
    "        ans = 0\n",
    "        if l<=m:\n",
    "            ans = self.query(node.left, lc,m,l,r)\n",
    "        if r>m:\n",
    "            ans = max(ans, self.query(node.right, m+1, rc, l,r))\n",
    "        return ans\n",
    "    def pushup(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "    def pushdown(self, node):\n",
    "        if not node.left: node.left=Node()\n",
    "        if not node.right: node.right=Node()\n",
    "        if node.add==0: return\n",
    "        node.left.val = node.add\n",
    "        node.right.val = node.add\n",
    "        node.left.add = node.add\n",
    "        node.right.add = node.add\n",
    "        node.add = 0\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        #ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cnt = self.query(self.root, 0, self.N, max(0, nums[i]-k), nums[i]-1)+1\n",
    "            self.update(self.root, 0, self.N, nums[i], nums[i], cnt)\n",
    "            #ans = max(ans, cnt)\n",
    "        return self.root.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线段树，[s，t)\n",
    "class TreeNode:\n",
    "    def __init__(self, val, s, t):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.s = s\n",
    "        self.t = t\n",
    "    def __repr__(self):\n",
    "        return 'TreeNode({}, {}, {}, {}, {})'.format(self.val, self.s, self.t, self.left, self.right)\n",
    "\n",
    "    def update(self, i, val):\n",
    "        if self.s == self.t - 1:\n",
    "            assert self.s == i\n",
    "            self.val = val\n",
    "            return val\n",
    "\n",
    "        m = (self.s + self.t) // 2\n",
    "        if self.left is None:\n",
    "            self.left = TreeNode(0, self.s, m)\n",
    "            self.right = TreeNode(0, m, self.t)\n",
    "        if i < m:\n",
    "            v = self.left.update(i, val)\n",
    "        else:\n",
    "            v = self.right.update(i, val)\n",
    "        if v > self.val:\n",
    "            self.val = v\n",
    "        return self.val\n",
    "\n",
    "    def get(self, l, r):\n",
    "        #print(self, l, r)\n",
    "        if l <= self.s and self.t <= r:\n",
    "            return self.val\n",
    "        m = (self.s + self.t) // 2\n",
    "        mx = 0\n",
    "        if l < m and self.left and (tmp := self.left.get(l, r)) > mx:\n",
    "            mx = tmp\n",
    "        if r > m and self.right and (tmp := self.right.get(l, r)) > mx:\n",
    "            mx = tmp\n",
    "        return mx\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        dp = TreeNode(0, 0, max(nums) + 1)\n",
    "        mx = dp.update(nums[0], 1)\n",
    "        for i in nums[1:]:\n",
    "            if (tmp := dp.update(i, dp.get(max(0, i - k), i) + 1)) > mx:\n",
    "                mx = tmp\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        m = max(nums)\n",
    "        dp = [0] * (m + 1)\n",
    "        root = SegTree()\n",
    "        for num in nums:\n",
    "            ref = root.query(root.root, 0, m, num - k, num - 1)     # 0 4 1 3\n",
    "            if ref >= dp[num]:\n",
    "                dp[num] = ref\n",
    "                root.update(root.root, 0, m, num, ref + 1)    \n",
    "        return root.root.val\n",
    "\n",
    "\n",
    "class Node:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.val = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "\n",
    "class SegTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def __addnode(self, node):\n",
    "        if not node.left : node.left = Node()\n",
    "        if not node.right : node.right = Node()\n",
    "    \n",
    "    def __push_up(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "    \n",
    "    def update(self, node, lo, hi, idx, val):\n",
    "        if lo == hi:\n",
    "            node.val = val\n",
    "            return \n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        if mid >= idx:\n",
    "            self.update(node.left, lo, mid, idx, val)\n",
    "        else:\n",
    "            self.update(node.right, mid + 1, hi, idx, val)\n",
    "        self.__push_up(node)\n",
    "\n",
    "    def query(self, node, lo, hi, left, right):\n",
    "        if left <= lo and right >= hi:\n",
    "            return node.val\n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        a = b = 0\n",
    "        if left <= mid:\n",
    "            a = self.query(node.left, lo, mid, left, right)\n",
    "        if mid < right:\n",
    "            b = self.query(node.right, mid + 1, hi, left, right)\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        m = max(nums)\n",
    "        dp = [0] * (m + 1)\n",
    "        root = SegTree()\n",
    "        for num in nums:\n",
    "            ref = root.query(root.root, 0, m, num - k, num - 1)     # 0 4 1 3\n",
    "            if ref >= dp[num]:\n",
    "                dp[num] = ref\n",
    "                root.update(root.root, 0, m, num, ref + 1)    \n",
    "        return root.root.val\n",
    "\n",
    "\n",
    "class Node:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.val = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "\n",
    "class SegTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def __addnode(self, node):\n",
    "        if not node.left:\n",
    "            node.left = Node()\n",
    "            node.right = Node()\n",
    "    \n",
    "    def __push_up(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "    \n",
    "    def update(self, node, lo, hi, idx, val):\n",
    "        if lo == hi:\n",
    "            node.val = val\n",
    "            return \n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        if mid >= idx:\n",
    "            self.update(node.left, lo, mid, idx, val)\n",
    "        else:\n",
    "            self.update(node.right, mid + 1, hi, idx, val)\n",
    "        self.__push_up(node)\n",
    "\n",
    "    def query(self, node, lo, hi, left, right):\n",
    "        if left <= lo and right >= hi:\n",
    "            return node.val\n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        a = b = 0\n",
    "        if left <= mid:\n",
    "            a = self.query(node.left, lo, mid, left, right)\n",
    "        if mid < right:\n",
    "            b = self.query(node.right, mid + 1, hi, left, right)\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        maxnum, minnum = float('-inf'), float('inf')\n",
    "        for num in nums:\n",
    "            minnum = min(minnum, num)\n",
    "            maxnum = max(maxnum, num)\n",
    "        tree = [None]*(4*maxnum)\n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                tree[t] = [0,l,r,0]\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            tree[t] = [0,l,r,0]\n",
    "            return\n",
    "        def pushdow(t):\n",
    "            lazy = tree[t][3]\n",
    "            tree[2*t][0] = lazy \n",
    "            tree[2*t][3] = lazy \n",
    "            tree[2*t+1][0] = lazy \n",
    "            tree[2*t+1][3] = lazy\n",
    "            tree[t][3] = 0\n",
    "            return\n",
    "        def update(t,ul,ur,x):\n",
    "            # if(ul > ur or tree[t] == None):\n",
    "            #     return\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ul <= l  and r <= ur):\n",
    "                tree[t][0] = x\n",
    "                tree[t][3] = x\n",
    "                return\n",
    "            if(lazy > 0):\n",
    "                pushdow(t)\n",
    "            m = (l+r)>>1\n",
    "            if(ul <= m):\n",
    "                update(2*t,ul,ur,x)\n",
    "            if(ur > m):\n",
    "                update(2*t+1,ul,ur,x)\n",
    "            tree[t][0] = max(tree[2*t][0],tree[2*t+1][0])\n",
    "            return \n",
    "\n",
    "        def query(t,ql,qr):\n",
    "            if(ql > qr or tree[t] == None):\n",
    "                return 0\n",
    "            v, l, r, lazy = tree[t]\n",
    "            if(ql <= l  and r <= qr):\n",
    "                return tree[t][0]\n",
    "            if(lazy > 0):\n",
    "                pushdow(t)\n",
    "            res = 0\n",
    "            m = (l+r)>>1\n",
    "            if(ql <= m):\n",
    "                res = max(res, query(2*t,ql,qr))\n",
    "            if(qr > m):\n",
    "                res = max(res, query(2*t+1,ql,qr))\n",
    "            return res\n",
    "        result = 1\n",
    "        build(1,minnum,maxnum)\n",
    "        for num in nums:\n",
    "            ql = max(minnum,num-k)\n",
    "            qr = num - 1\n",
    "            res = query(1,ql,qr) + 1\n",
    "            update(1,num,num,res)\n",
    "            result = max(result, res)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeRangeMax:\n",
    "    def __init__(self):\n",
    "        self.cover = defaultdict(int)\n",
    "        self.lazy = defaultdict(int)\n",
    "        self.count = 0\n",
    "\n",
    "    def push_down(self, i):\n",
    "        if self.lazy[i]:\n",
    "            self.cover[2 * i] = self.lazy[i]\n",
    "            self.cover[2 * i + 1] = self.lazy[i]\n",
    "\n",
    "            self.lazy[2 * i] = self.lazy[i]\n",
    "            self.lazy[2 * i + 1] = self.lazy[i]\n",
    "\n",
    "            self.lazy[i] = 0\n",
    "\n",
    "    def update(self, left, r, s, t, val, i):\n",
    "        if left <= s and t <= r:\n",
    "            if val > self.cover[i]:\n",
    "                self.cover[i] = val\n",
    "                self.lazy[i] = val\n",
    "            return\n",
    "\n",
    "        self.push_down(i)\n",
    "        m = s + (t - s) // 2\n",
    "        if left <= m:\n",
    "            self.update(left, r, s, m, val, 2 * i)\n",
    "        if r > m:\n",
    "            self.update(left, r, m + 1, t, val, 2 * i + 1)\n",
    "        self.cover[i] = max(self.cover[2 * i], self.cover[2 * i + 1])\n",
    "        return\n",
    "\n",
    "    def query(self, left, r, s, t, i):\n",
    "        if left <= s and t <= r:\n",
    "            return self.cover[i]\n",
    "        self.push_down(i)\n",
    "        m = s + (t - s) // 2\n",
    "        res = 0\n",
    "        if left <= m:\n",
    "            cur = self.query(left, r, s, m, 2 * i)\n",
    "            res = res if res > cur else cur\n",
    "        if r > m:\n",
    "            cur = self.query(left, r, m + 1, t, 2 * i + 1)\n",
    "            res = res if res > cur else cur\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = max(nums)\n",
    "        segment = SegmentTreeRangeMax()\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            low = 0 if 0 > num - k else num - k\n",
    "            length = segment.query(low, num - 1, 0, n, 1)\n",
    "            ans = ans if ans > length + 1 else length + 1\n",
    "            segment.update(num, num, 0, n, length + 1, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        _max = max(nums)\n",
    "        maxes = [0]*((_max+1)*4)\n",
    "        def query(l, r, off, ql, qr):\n",
    "            if qr < l or ql > r: return 0\n",
    "            if ql <= l and qr >= r: return maxes[off]\n",
    "            m = (l + r)>>1\n",
    "            v = 0\n",
    "            if ql <= m:\n",
    "                v = query(l, m, off<<1, ql, qr)\n",
    "            if qr >= m + 1:\n",
    "                v = max(v, query(m+1, r, off*2+1, ql, qr))\n",
    "            return v\n",
    "        def update(n, v):\n",
    "            l, r, off = 1, _max, 1\n",
    "            stack = [off]\n",
    "            while r > l:\n",
    "                m = (l + r)>>1\n",
    "                if n<=m:\n",
    "                    r = m\n",
    "                    off <<= 1\n",
    "                else:\n",
    "                    l = m+1\n",
    "                    off = off*2+1\n",
    "                stack.append(off)\n",
    "            maxes[off] = v\n",
    "            stack.pop()\n",
    "            while stack:\n",
    "                off = stack.pop()\n",
    "                maxes[off] = max(maxes[off<<1], maxes[off*2+1])\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            lastMax = query(1, _max, 1, max(n-k, 1), n-1)\n",
    "            update(n, lastMax + 1)\n",
    "            res = max(res, lastMax + 1)\n",
    "        return res\n",
    "        # R[n] = max(R[m])+1 when nums[m] >= nums[n] - k "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        l = set(nums)\n",
    "        for i in nums:\n",
    "            l.add(i + k)\n",
    "        l = list(l)\n",
    "        l.sort()\n",
    "        s = {i: ind + 1 for ind, i in enumerate(l)}\n",
    "        d, n, res = {}, len(s), 0\n",
    "        dps = [0] * (4 * n + 1)\n",
    "        ups = [0] * (4 * n + 1)\n",
    "\n",
    "        def _pushdown(rt):\n",
    "            if ups[rt]:\n",
    "                dps[rt << 1] = ups[rt]\n",
    "                ups[rt << 1] = ups[rt]\n",
    "                dps[rt << 1 | 1] = ups[rt]\n",
    "                ups[rt << 1 | 1] = ups[rt]\n",
    "                ups[rt] = 0\n",
    "\n",
    "        def _update(L, R, C, l, r, rt):\n",
    "            if l >= L and r <= R:\n",
    "                dps[rt] = C\n",
    "                ups[rt] = C\n",
    "                return\n",
    "            mid = l + ((r - l) >> 1)\n",
    "            _pushdown(rt)\n",
    "            if l <= R and mid >= L:\n",
    "                _update(L, R, C, l, mid, rt << 1)\n",
    "            if mid + 1 <= R and r >= L:\n",
    "                _update(L, R, C, mid + 1, r, rt << 1 | 1)\n",
    "            dps[rt] = max(dps[rt << 1], dps[rt << 1 | 1])\n",
    "\n",
    "        def _query(L, R, l, r, rt):\n",
    "            if l >= L and r <= R:\n",
    "                return dps[rt]\n",
    "            mid = l + ((r - l) >> 1)\n",
    "            _pushdown(rt)\n",
    "            imax = 0\n",
    "            if l <= R and mid >= L:\n",
    "                imax = max(imax, _query(L, R, l, mid, rt << 1))\n",
    "            if mid + 1 <= R and r >= L:\n",
    "                imax = max(imax, _query(L, R, mid + 1, r, rt << 1 | 1))\n",
    "            return imax\n",
    "\n",
    "        for i in nums[::-1]:\n",
    "            tmp = _query(s[i] + 1, s[i + k], 1, n, 1) + 1\n",
    "            res = max(tmp, res)\n",
    "            _update(s[i], s[i], tmp, 1, n, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=0, start=0, end=1, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        mi, mx = min(nums), max(nums)\n",
    "        dp = [0] * (mx - mi + 1)\n",
    "        n = len(dp)\n",
    "        def build_tree(lo, hi):\n",
    "            if lo == hi - 1:\n",
    "                return Node(dp[lo], lo, hi)\n",
    "            mid = (lo + hi) // 2\n",
    "            left = build_tree(lo, mid)\n",
    "            right = build_tree(mid, hi)\n",
    "            return Node(max(left.val, right.val), lo, hi, left, right)\n",
    "        root = build_tree(0, n)\n",
    "        def query(node, lo, hi):\n",
    "            if lo == hi: return 0\n",
    "            if lo == node.start and hi == node.end:\n",
    "                return node.val\n",
    "            mid = (node.start + node.end) // 2\n",
    "            if hi <= mid:\n",
    "                return query(node.left, lo, hi)\n",
    "            if lo >= mid:\n",
    "                return query(node.right, lo, hi)\n",
    "            return max(query(node.left, lo, mid), query(node.right, mid, hi))\n",
    "        def update(node, i, val):\n",
    "            if node.start == i == node.end - 1:\n",
    "                dp[i] = node.val = val\n",
    "                return\n",
    "            mid = (node.start + node.end) // 2\n",
    "            if i < mid:\n",
    "                update(node.left, i, val)\n",
    "            else:\n",
    "                update(node.right, i, val)\n",
    "            node.val = max(node.left.val, node.right.val)\n",
    "        for x in nums:\n",
    "            x -= mi\n",
    "            res = 1 + query(root, max(0, x - k), x)\n",
    "            if res > dp[x]:\n",
    "                update(root, x, res)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTreeNode:\n",
    "    def __init__(self, a,b):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.start = a\n",
    "        self.end = b\n",
    "        self.info = 0\n",
    "        \n",
    "        if a == b:\n",
    "            self.info = 0\n",
    "            return\n",
    "\n",
    "        mid = (a + b) // 2\n",
    "        if self.left is None:\n",
    "            self.left = SegTreeNode(a, mid)\n",
    "            self.right = SegTreeNode(mid + 1, b)\n",
    "            self.info = 0\n",
    "\n",
    "    def updateSingle(self, id, val):\n",
    "        if id < self.start or id > self.end:\n",
    "            return\n",
    "        if self.start == self.end:\n",
    "            self.info = val\n",
    "            return\n",
    "        self.left.updateSingle(id, val)\n",
    "        self.right.updateSingle(id, val)\n",
    "        self.info = max(self.left.info , self.right.info)\n",
    "\n",
    "    def queryRange(self, a, b):\n",
    "        if b < self.start or a > self.end:\n",
    "            return 0\n",
    "        if a <= self.start and b >= self.end:\n",
    "            return self.info\n",
    "        return max(self.left.queryRange(a, b) , self.right.queryRange(a, b))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = max(nums)\n",
    "        root = SegTreeNode(0, n)\n",
    "        rets = 0\n",
    "        for i in nums:\n",
    "            temp = root.queryRange(i-k,i-1)\n",
    "            rets = max(rets,temp+1)\n",
    "            root.updateSingle(i,temp+1)\n",
    "        return rets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        st = ST([0 for _ in range(max(nums) + 1)])\n",
    "        for i in range(len(nums)):\n",
    "            l, r = max(nums[i] - k, 0), max(nums[i] - 1, 0)\n",
    "            st.modify(nums[i], st.query(l, r) + 1)\n",
    "        return st.query(0, max(nums))\n",
    "class Node:\n",
    "    def __init__(self, st, ed, l, r, v):\n",
    "        self.st = st\n",
    "        self.ed = ed\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.v = v\n",
    "class ST:\n",
    "    def __init__(self, arr):\n",
    "        self.root = self.build(arr, 0, len(arr) - 1)\n",
    "    def build(self, arr, L, R):\n",
    "        if L == R:\n",
    "            return Node(L, R, None, None, arr[L])\n",
    "        node = Node(L, R, None, None, None)\n",
    "        M = (L + R) >> 1\n",
    "        node.l = self.build(arr, L, M)\n",
    "        node.r = self.build(arr, M + 1, R)\n",
    "        node.v = max(node.l.v, node.r.v)\n",
    "        return node\n",
    "    def modify(self, i, v):\n",
    "        self.modify_helper(self.root, i, v)\n",
    "    def modify_helper(self, node, i, v):\n",
    "        if node.st == node.ed:\n",
    "            node.v = v\n",
    "        else:\n",
    "            m = (node.st + node.ed) >> 1\n",
    "            if i <= m:\n",
    "                self.modify_helper(node.l, i, v)\n",
    "            else:\n",
    "                self.modify_helper(node.r, i, v)\n",
    "            node.v = max(node.l.v, node.r.v)\n",
    "    def query(self, l, r):\n",
    "        return self.query_helper(self.root, l, r) \n",
    "    def query_helper(self, node, l, r):\n",
    "        if node.st == l and node.ed == r:\n",
    "            return node.v\n",
    "        m = (node.st + node.ed) >> 1\n",
    "        if m >= r:\n",
    "            return self.query_helper(node.l, l, r)\n",
    "        elif m < l:\n",
    "            return self.query_helper(node.r, l, r)\n",
    "        else:\n",
    "            return max(self.query_helper(node.l, l, m), self.query_helper(node.r, m + 1, r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class SegTreeNode:\n",
    "    def __init__(self, val=0, r1=0, r2=0):\n",
    "        self.val = val\n",
    "        self.r1 = r1\n",
    "        self.r2 = r2\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        self.min_v, self.max_v = min(nums), max(nums)\n",
    "        #Step1 构建树 初始时，所有点的长度都是0\n",
    "        self.root = self.build(self.min_v, self.max_v)\n",
    "\n",
    "        dp = [0]*n\n",
    "        max_res = 0\n",
    "        for i in range(n):\n",
    "            cur = nums[i]\n",
    "            max_length = self.search(cur-k, cur-1)\n",
    "            dp[i] = 1+max_length\n",
    "            max_res = max(max_res, dp[i])\n",
    "            self.update(nums[i], dp[i])\n",
    "        return max_res\n",
    "\n",
    "    def build(self, rl, rr):\n",
    "        if rl==rr:\n",
    "            return SegTreeNode(val=0, r1=rl, r2=rr)\n",
    "        mid = (rl+rr)//2\n",
    "        root = SegTreeNode(val=0, r1=rl, r2=rr)\n",
    "        root.left = self.build(rl, mid)\n",
    "        root.right = self.build(mid+1, rr)\n",
    "        return root\n",
    "\n",
    "    # 单点修改\n",
    "    def update(self, index, new_v):\n",
    "\n",
    "        def mup(node):\n",
    "            rl, rr = node.r1, node.r2\n",
    "            mid = (rl+rr)//2\n",
    "            if rl==rr:\n",
    "                node.val = max(node.val, new_v)\n",
    "                return\n",
    "            elif index<=mid:\n",
    "                mup(node.left)\n",
    "            else:\n",
    "                mup(node.right)\n",
    "            node.val = max(node.left.val, node.right.val)\n",
    "\n",
    "        mup(self.root)\n",
    "    \n",
    "    # 查询区间最大值\n",
    "    def search(self, l,r):\n",
    "        if r<self.min_v: return 0\n",
    "        l = max(l, self.min_v)\n",
    "\n",
    "        def help(node, rl, rr)->int:\n",
    "            if rl==node.r1 and rr==node.r2:\n",
    "                return node.val\n",
    "            \n",
    "            res = 0\n",
    "            mid = (node.r1+node.r2)//2\n",
    "            # 全部在左边\n",
    "            if rr<=mid:\n",
    "                res = max(res, help(node.left, rl, rr))\n",
    "            # 全部右边\n",
    "            elif rl>=mid+1:\n",
    "                res = max(res, help(node.right, rl, rr))\n",
    "            # 被mid截断\n",
    "            else:\n",
    "                left_max = help(node.left, rl, mid)\n",
    "                right_max = help(node.right, mid+1, rr)\n",
    "                res = max(res, left_max, right_max)\n",
    "            return res\n",
    "        \n",
    "        return help(self.root, l, r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r,v=0):\n",
    "        self.l, self.r = l, r\n",
    "        self.v = v\n",
    "class Segment_Tree:\n",
    "    def __init__(self, n):\n",
    "        self.tr = [None] * (4 * n)\n",
    "        self.build(1, 1, n)\n",
    "    def build(self, u, l, r):\n",
    "        self.tr[u] = Node(l, r)\n",
    "        if l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            self.build(u << 1, l, mid)\n",
    "            self.build(u << 1 | 1, mid + 1, r)\n",
    "    \n",
    "    def update(self, u, x, v):\n",
    "        if self.tr[u].l == x and self.tr[u].r == x:\n",
    "            self.tr[u].v = v # self.tr[u].v += v \n",
    "            return\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        if x <= mid:\n",
    "            self.update(u << 1, x, v)\n",
    "        else:\n",
    "            self.update(u << 1 | 1, x, v)\n",
    "        self.pushup(u)\n",
    "    \n",
    "    def query(self, u, l , r):\n",
    "        if l <= self.tr[u].l and self.tr[u].r <= r:\n",
    "            return self.tr[u].v\n",
    "        mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "        l_ = r_ = 0\n",
    "        if l <= mid:\n",
    "            l_ = self.query(u << 1, l, r)\n",
    "        if r > mid:\n",
    "            r_ =  self.query(u << 1 | 1, l, r)\n",
    "        return max(l_, r_)\n",
    "    \n",
    "    def pushup(self, u):\n",
    "        self.tr[u].v = max(self.tr[u << 1].v , self.tr[u << 1 | 1].v)\n",
    "        \n",
    "class Solution(object):\n",
    "    def lengthOfLIS(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.max_range = max(nums) + 6\n",
    "        self.seg_tree = Segment_Tree(self.max_range)\n",
    "        for n in nums:\n",
    "            cnt = self.seg_tree.query(1,  max(0, n -k) + 1, n - 1 + 1)\n",
    "            # print(cnt)\n",
    "            self.seg_tree.update(1, n+1, cnt + 1)\n",
    "            \n",
    "        return self.seg_tree.query(1, 1, self.max_range + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        self.t = LAZY_SEGMENTTREE(\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            reduce_op = lambda val1,val2:  max(val1 , val2),\n",
    "            lazy_op = lambda lazy0,lz :   max(lazy0,lz), \n",
    "            lazy_val = lambda l,r,lz,val0: max(lz,val0) \n",
    "        ) \n",
    "        mi = min(nums) - k \n",
    "        mx = max(nums)\n",
    "        for x in nums:\n",
    "            bf = self.t.query(x-k,x-1,mi ,mx,1) \n",
    "            self.t.update(x,x,mi ,mx,1,bf+1) \n",
    "        return self.t.query(mi ,mx ,mi ,mx,1) \n",
    "class LAZY_SEGMENTTREE:\n",
    "    def __init__(self,\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            reduce_op = lambda val1,val2:  val1 + val2,\n",
    "            lazy_op = lambda lazy0,lz :  lazy0 + lz, \n",
    "            lazy_val = lambda l,r,lz,val0: val0+lz*(r-l+1)\n",
    "        ):\n",
    "        self.defaultval = defaultval\n",
    "        self.defaultlazy = defaultlazy\n",
    "        self.reduce_op = reduce_op\n",
    "        self.lazy_op = lazy_op\n",
    "        self.lazy_val = lazy_val\n",
    "        self.val = defaultdict(lambda:defaultval)\n",
    "        self.lazy = defaultdict(lambda:defaultlazy) \n",
    "    def update(self,start, end, l, r, i, lz):  \n",
    "        if start <= l and r <= end:  \n",
    "            self.val[i] = self.lazy_val(l,r,lz,self.val[i])   \n",
    "            self.lazy[i] = self.lazy_op(self.lazy[i],lz)\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            if self.lazy[i] != self.defaultlazy :\n",
    "                self.val[i*2] = self.lazy_val(l, mid,self.lazy[i],self.val[i*2])\n",
    "                self.lazy[i*2]   = self.lazy_op(self.lazy[i * 2],self.lazy[i])\n",
    "                self.val[i*2+1] = self.lazy_val(mid + 1, r,self.lazy[i],self.val[i*2+1])\n",
    "                self.lazy[i*2+1] = self.lazy_op(self.lazy[i*2+1],self.lazy[i])\n",
    "                self.lazy[i] = self.defaultlazy\n",
    "            if mid >= start : self.update(start, end, l, mid, i * 2,lz)\n",
    "            if mid+1 <= end : self.update(start, end, mid + 1, r, i * 2 + 1,lz) \n",
    "            self.val[i] = self.reduce_op(self.val[i*2] , self.val[i*2+1])\n",
    "    def query(self,start, end, l, r, i):\n",
    "        if r < start or end < l: return self.defaultval\n",
    "        if start <= l and r <= end: return self.val[i]\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            res =  self.lazy_val( \n",
    "                max(l,start),  min(r,end), self.lazy[i]  ,\n",
    "                self.reduce_op(self.query(start, end, l, mid, i * 2) , self.query(start, end, mid + 1, r, i * 2 + 1))\n",
    "            ) \n",
    "            return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        tree = LAZY_SEGMENTTREE(\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            left= 0, right = max(nums),\n",
    "            reduce_op = lambda val1,val2:  val1 if val1 > val2 else val2,\n",
    "            lazy_op = lambda lazy0,lz :   lazy0 if lazy0 > lz else lz, \n",
    "            lazy_val = lambda l,r,lz,val0: lz if lz > val0 else val0 \n",
    "        ) \n",
    "        for x in nums:\n",
    "            q = tree.query( max(0,x-k) , x-1 ) \n",
    "            tree.update(x,x,q+1) \n",
    "        return tree.query(0,max(nums))\n",
    "class LAZY_SEGMENTTREE:\n",
    "    def __init__(self,\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            left = 0, right = 10**9,\n",
    "            reduce_op = lambda val1,val2:  val1 + val2,\n",
    "            lazy_op = lambda lazy0,lz :  lazy0 + lz, \n",
    "            lazy_val = lambda l,r,lz,val0: val0+lz*(r-l+1)\n",
    "        ):\n",
    "        self.defaultval = defaultval\n",
    "        self.defaultlazy = defaultlazy\n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.reduce_op = reduce_op\n",
    "        self.lazy_op = lazy_op\n",
    "        self.lazy_val = lazy_val\n",
    "        self.val = defaultdict(lambda:defaultval)\n",
    "        self.lazy = defaultdict(lambda:defaultlazy) \n",
    "    def update(self,start,end,lz):\n",
    "        return self._update(start,end,self.left,self.right,1,lz) \n",
    "    def query(self,start,end):\n",
    "        return self._query(start,end,self.left,self.right,1)\n",
    "    def _update(self,start, end, l, r, i, lz):  \n",
    "        if start <= l and r <= end:  \n",
    "            self.val[i] = self.lazy_val(l,r,lz,self.val[i])   \n",
    "            self.lazy[i] = self.lazy_op(self.lazy[i],lz)\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            if self.lazy[i] != self.defaultlazy :\n",
    "                self.val[i*2] = self.lazy_val(l, mid,self.lazy[i],self.val[i*2])\n",
    "                self.lazy[i*2]   = self.lazy_op(self.lazy[i * 2],self.lazy[i])\n",
    "                self.val[i*2+1] = self.lazy_val(mid + 1, r,self.lazy[i],self.val[i*2+1])\n",
    "                self.lazy[i*2+1] = self.lazy_op(self.lazy[i*2+1],self.lazy[i])\n",
    "                self.lazy[i] = self.defaultlazy\n",
    "            if mid >= start : self._update(start, end, l, mid, i * 2,lz)\n",
    "            if mid+1 <= end : self._update(start, end, mid + 1, r, i * 2 + 1,lz) \n",
    "            self.val[i] = self.reduce_op(self.val[i*2] , self.val[i*2+1])\n",
    "    def _query(self,start, end, l, r, i):\n",
    "        if r < start or end < l: return self.defaultval\n",
    "        if start <= l and r <= end: return self.val[i]\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            res =  self.lazy_val( \n",
    "                max(l,start),  min(r,end), self.lazy[i]  ,\n",
    "                self.reduce_op(self._query(start, end, l, mid, i * 2) , \n",
    "                            self._query(start, end, mid + 1, r, i * 2 + 1))\n",
    "            ) \n",
    "            return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_ = lambda x,y : x if x > y else y \n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        tree = LAZY_SEGMENTTREE(\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            left= 0, right = max(nums),\n",
    "            reduce_op = lambda val1,val2:  val1 if val1 > val2 else val2,\n",
    "            lazy_op = lambda lazy0,lz :   lazy0 if lazy0 > lz else lz, \n",
    "            lazy_val = lambda l,r,lz,val0: lz if lz > val0 else val0 \n",
    "        ) \n",
    "        for x in nums:\n",
    "            res = tree.query(max(0,x-k),x-1)\n",
    "            tree.update(x,x,res+1)\n",
    "        return tree.query(0,max(nums))\n",
    "        \n",
    "class LAZY_SEGMENTTREE:\n",
    "    def __init__(self,\n",
    "            defaultval = 0 ,\n",
    "            defaultlazy = 0 , \n",
    "            left = 0, right = 10**9,\n",
    "            reduce_op = lambda val1,val2:  val1 + val2,\n",
    "            lazy_op = lambda lazy0,lz :  lazy0 + lz, \n",
    "            lazy_val = lambda l,r,lz,val0: val0+lz*(r-l+1)\n",
    "        ):\n",
    "        self.defaultval = defaultval\n",
    "        self.defaultlazy = defaultlazy\n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.reduce_op = reduce_op\n",
    "        self.lazy_op = lazy_op\n",
    "        self.lazy_val = lazy_val\n",
    "        self.val = defaultdict(lambda:defaultval)\n",
    "        self.lazy = defaultdict(lambda:defaultlazy) \n",
    "    def update(self,start,end,lz):\n",
    "        return self._update(start,end,self.left,self.right,1,lz) \n",
    "    def query(self,start,end):\n",
    "        return self._query(start,end,self.left,self.right,1)\n",
    "    def _update(self,start, end, l, r, i, lz):  \n",
    "        if start <= l and r <= end:  \n",
    "            self.val[i] = self.lazy_val(l,r,lz,self.val[i])   \n",
    "            self.lazy[i] = self.lazy_op(self.lazy[i],lz)\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            if self.lazy[i] != self.defaultlazy :\n",
    "                self.val[i*2] = self.lazy_val(l, mid,self.lazy[i],self.val[i*2])\n",
    "                self.lazy[i*2]   = self.lazy_op(self.lazy[i * 2],self.lazy[i])\n",
    "                self.val[i*2+1] = self.lazy_val(mid + 1, r,self.lazy[i],self.val[i*2+1])\n",
    "                self.lazy[i*2+1] = self.lazy_op(self.lazy[i*2+1],self.lazy[i])\n",
    "                self.lazy[i] = self.defaultlazy\n",
    "            if mid >= start : self._update(start, end, l, mid, i * 2,lz)\n",
    "            if mid+1 <= end : self._update(start, end, mid + 1, r, i * 2 + 1,lz) \n",
    "            self.val[i] = self.reduce_op(self.val[i*2] , self.val[i*2+1])\n",
    "    def _query(self,start, end, l, r, i):\n",
    "        if r < start or end < l: return self.defaultval\n",
    "        if start <= l and r <= end: return self.val[i]\n",
    "        else:\n",
    "            mid = (l + r) // 2\n",
    "            res =  self.lazy_val( \n",
    "                max(l,start),  min(r,end), self.lazy[i]  ,\n",
    "                self.reduce_op(self._query(start, end, l, mid, i * 2) , \n",
    "                            self._query(start, end, mid + 1, r, i * 2 + 1))\n",
    "            ) \n",
    "            return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, down, up):\n",
    "        self.down = down\n",
    "        self.up = up\n",
    "        self.mid = down + up >> 1\n",
    "        self.maxi = self.mini = 0\n",
    "        self.left = self.right = None\n",
    "        if down != up:\n",
    "            self.left = SegTree(down, self.mid)\n",
    "            self.right = SegTree(self.mid+1, up)\n",
    "            \n",
    "    def add(self, down, up, val):\n",
    "        if self.mini >= val: return\n",
    "        if self.maxi == self.mini:\n",
    "            if down == self.down and up == self.up:\n",
    "                self.maxi = self.mini = val\n",
    "                return\n",
    "            self.left.maxi = self.left.mini = self.right.maxi = self.right.mini = self.maxi\n",
    "        if self.mid < down:\n",
    "            self.right.add(down, up, val)\n",
    "        elif self.mid >= up:\n",
    "            self.left.add(down, up, val)\n",
    "        else:\n",
    "            self.left.add(down, self.mid, val)\n",
    "            self.right.add(self.mid+1, up, val)\n",
    "        self.maxi = max(self.left.maxi, self.right.maxi)\n",
    "        self.mini = min(self.left.mini, self.right.mini)\n",
    "    \n",
    "    def search(self, i):\n",
    "        if self.maxi == self.mini: return self.maxi\n",
    "        return self.left.search(i) if self.mid >= i else self.right.search(i)\n",
    "        \n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        down, up = min(nums), max(nums) + 1\n",
    "        root = SegTree(down, up)\n",
    "        for i in nums:\n",
    "            val = root.search(i) + 1\n",
    "            root.add(i+1, min(i+k, up), val)\n",
    "        return root.maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        u = max(nums)\n",
    "        mx = [0] * (4 * u)\n",
    "\n",
    "        def modify(o, l, r, i, val):\n",
    "            if l == r:\n",
    "                mx[o] = val\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            if i <= mid:\n",
    "                modify(o*2, l, mid, i, val)\n",
    "            else:\n",
    "                modify(o*2 + 1, mid + 1, r, i, val)\n",
    "            mx[o] = max(mx[o*2], mx[o*2+1])\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if L <= l and R >= r:\n",
    "                return mx[o]\n",
    "            res = 0\n",
    "            mid = (l + r) // 2\n",
    "            if L <= mid:\n",
    "                res = query(o*2, l, mid, L, R)\n",
    "            if R > mid:\n",
    "                res = max(res, query(o*2+1, mid + 1, r, L, R))\n",
    "            return res \n",
    "\n",
    "        for n in nums:\n",
    "            if n == 1:\n",
    "                modify(1, 1, u, 1, 1)\n",
    "            else:\n",
    "                res = 1 + query(1, 1, u, max(n - k, 1), n - 1)\n",
    "                modify(1, 1, u, n, res)\n",
    "        return mx[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n=max(nums)\n",
    "        class node:\n",
    "            def __init__(self,l,r,v,mx):\n",
    "                self.l=l\n",
    "                self.r=r\n",
    "                self.v=v\n",
    "                self.mx=mx\n",
    "        tr=[node for _ in range(4*n)]\n",
    "        def build(u:int,l:int,r:int)->None:\n",
    "            if l==r:tr[u]=node(l,r,0,0)\n",
    "            else:\n",
    "                tr[u]=node(l,r,0,0)\n",
    "                mid=l+r>>1\n",
    "                build(u<<1,l,mid)\n",
    "                build(u<<1|1,mid+1,r)\n",
    "        def pushup(u:int)->None:\n",
    "            tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx)\n",
    "        def modify(u:int,x:int,v:int)->None:\n",
    "            if tr[u].l==tr[u].r and tr[u].l==x:\n",
    "                tr[u].mx=v\n",
    "                return\n",
    "            else:\n",
    "                mid=tr[u].l+tr[u].r>>1\n",
    "                if x<=mid:modify(u<<1,x,v)\n",
    "                else:modify(u<<1|1,x,v)\n",
    "                pushup(u)\n",
    "        def query(u:int,l:int,r:int)->int:\n",
    "            if tr[u].l>=l and tr[u].r<=r:\n",
    "                return tr[u].mx\n",
    "            else:\n",
    "                mid=tr[u].l+tr[u].r>>1\n",
    "                res=0\n",
    "                if l<=mid:res=max(res,query(u<<1,l,r))\n",
    "                if r>mid:res=max(res,query(u<<1|1,l,r))\n",
    "                return res\n",
    "        \n",
    "        ans=1\n",
    "        build(1,1,n)\n",
    "        for x in nums:\n",
    "            if x == 1:\n",
    "                modify(1,x,x)\n",
    "            else:\n",
    "                res = 1 + query(1,max(1,x-k),x-1)\n",
    "                ans=max(ans,res)\n",
    "                modify(1,x,res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        n=max(nums)\n",
    "        class node:\n",
    "            def __init__(self,l,r,v,mx):\n",
    "                self.l=l\n",
    "                self.r=r\n",
    "                self.v=v\n",
    "                self.mx=mx\n",
    "        tr=[node for _ in range(4*n)]\n",
    "        def build(u:int,l:int,r:int)->None:\n",
    "            if l==r:tr[u]=node(l,r,0,0)\n",
    "            else:\n",
    "                tr[u]=node(l,r,0,0)\n",
    "                mid=l+r>>1\n",
    "                build(u<<1,l,mid)\n",
    "                build(u<<1|1,mid+1,r)\n",
    "        def pushup(u:int)->None:\n",
    "            tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx)\n",
    "        def modify(u:int,x:int,v:int)->None:\n",
    "            if tr[u].l==tr[u].r and tr[u].l==x:\n",
    "                tr[u].mx=v\n",
    "                return\n",
    "            else:\n",
    "                mid=tr[u].l+tr[u].r>>1\n",
    "                if x<=mid:modify(u<<1,x,v)\n",
    "                else:modify(u<<1|1,x,v)\n",
    "                pushup(u)\n",
    "        def query(u:int,l:int,r:int)->int:\n",
    "            if tr[u].l>=l and tr[u].r<=r:\n",
    "                return tr[u].mx\n",
    "            else:\n",
    "                mid=tr[u].l+tr[u].r>>1\n",
    "                res=0\n",
    "                if l<=mid:res=max(res,query(u<<1,l,r))\n",
    "                if r>mid:res=max(res,query(u<<1|1,l,r))\n",
    "                return res\n",
    "        \n",
    "        ans=1\n",
    "        build(1,1,n)\n",
    "        for x in nums:\n",
    "            if x==1:\n",
    "                modify(1,x,1)\n",
    "            else:\n",
    "                res = 1 + query(1,max(1,x-k),x-1)\n",
    "                ans=max(ans,res)\n",
    "                modify(1,x,res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int], k: int) -> int:\n",
    "        t = {}\n",
    "        def u(n, l, r, val, idx):\n",
    "            if n < l or n > r:\n",
    "                return\n",
    "            p = t.get(idx, 0)\n",
    "            t[idx] = max(p, val)\n",
    "            if l == r:\n",
    "                return\n",
    "            mi = (l + r) // 2\n",
    "            if n <= mi:\n",
    "                u(n, l, mi, val, 2 * idx)\n",
    "            else:\n",
    "                u(n, mi + 1, r, val, 2 * idx + 1)\n",
    "\n",
    "        def g(st, en, l, r, idx):\n",
    "            if en < l or st > r or idx not in t:\n",
    "                return 0\n",
    "            if st <= l and en >= r:\n",
    "                return t[idx]\n",
    "            mi = (l + r) // 2\n",
    "            return max(g(st, en, l, mi, 2 * idx), g(st, en, mi + 1, r, 2 * idx + 1))\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            c = g(n - k, n - 1, 0, 100000, 1)\n",
    "            c += 1\n",
    "            u(n, 0, 100000, c, 1)\n",
    "            res = max(res, c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, start, end, val=0) -> None:\n",
    "        self.start = start \n",
    "        self.end = end \n",
    "        self.mid = math.floor((self.start + self.end) / 2)\n",
    "        self.val = val \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.lazy = 0 \n",
    "        \n",
    "    def update(self, l, r, val):\n",
    "        if l <= self.start and self.end <= r:\n",
    "            self.val = val\n",
    "            self.lazy = val \n",
    "            return \n",
    "     \n",
    "       \n",
    "        self.pushdown()\n",
    "        if l <= self.mid:\n",
    "            self.left.update(l, r, val)\n",
    "        if r >= self.mid + 1:\n",
    "            self.right.update(l, r, val)\n",
    "        self.pushup()\n",
    "       \n",
    "    def query(self, l, r):\n",
    "        if r < l:\n",
    "            return 0\n",
    "        if l <= self.start and self.end <= r:\n",
    "            return self.val\n",
    "       \n",
    "        self.pushdown()\n",
    "        ans = 0 \n",
    "        if l <= self.mid:\n",
    "            ans = max(ans, self.left.query(l, r))\n",
    "        if r >= self.mid + 1:\n",
    "            ans = max(ans, self.right.query(l, r))\n",
    "        return ans \n",
    "        \n",
    "    def pushup(self):\n",
    "        self.val = max(self.left.val, self.right.val)\n",
    "        \n",
    "    def pushdown(self):\n",
    "      \n",
    "        if not self.left:\n",
    "            self.left = SegTree(self.start, self.mid)\n",
    "        if not self.right:\n",
    "            self.right = SegTree(self.mid+1, self.end)\n",
    "        if self.lazy == 0:\n",
    "            return \n",
    "        \n",
    "        self.left.lazy = self.lazy \n",
    "        self.left.val = (self.mid-self.start+1)*self.lazy \n",
    "        self.right.lazy = self.lazy \n",
    "        self.right.val = (self.end-self.mid)*self.lazy \n",
    "        self.lazy = 0\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums, k) -> int:\n",
    "        mx = max(nums)\n",
    "        seg = SegTree(1, mx, 0)\n",
    "        for i, x in enumerate(nums):\n",
    "            s = seg.query(max(1, x-k), x-1)\n",
    "            seg.update(x, x, s+1)\n",
    "\n",
    "        return seg.query(1, mx+1)\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
